JavaScript로 두 배열의 데카르트 곱(Cartesian Product) 계산하기

데카르트 곱(Cartesian Product)이란?

두 집합(배열) A와 B의 데카르트 곱은 A × B로 표기하며, 첫 번째 요소 a가 A에 속하고 두 번째 요소 b가 B에 속하는 모든 순서쌍 (a, b)의 집합을 의미합니다.

좀 더 쉽게 설명하면, 두 배열의 데카르트 곱은 '첫 번째 요소는 첫 번째 배열에서, 두 번째 요소는 두 번째 배열에서 가져온' 가능한 모든 두 요소 조합의 배열이라고 할 수 있습니다.

예를 들어, 다음과 같은 두 개의 배열이 있다고 가정해 보겠습니다.

const arr1 = [1, 2, 3];
const arr2 = [4, 5];

이 두 배열의 데카르트 곱은 다음과 같습니다.

const product = [[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]];

첫 번째 배열의 각 요소(1, 2, 3)가 두 번째 배열의 모든 요소(4, 5)와 차례대로 짝을 이루어 총 6개(3 × 2)의 순서쌍이 만들어지는 것을 확인할 수 있습니다.

구현 예제

데카르트 곱은 이중 반복문(for loop)을 사용하여 간단하게 구현할 수 있습니다. 바깥쪽 반복문으로 첫 번째 배열을 순회하고, 안쪽 반복문으로 두 번째 배열을 순회하면서 각 요소를 짝지어 주면 됩니다.

const arr1 = [1, 2, 3];
const arr2 = [4, 5];

const cartesianProduct = (arr1, arr2) => {
    const res = [];
    for(let i = 0; i < arr1.length; i++){
        for(let j = 0; j < arr2.length; j++){
            res.push(
                [arr1[i]].concat(arr2[j])
            );
        };
    };
    return res;
};

console.log(cartesianProduct(arr1, arr2));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

[ [ 1, 4 ], [ 1, 5 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ] ]

참고: 시간 복잡도

데카르트 곱의 결과 배열 크기는 두 배열 길이의 곱(|A| × |B|)만큼 커지므로, 시간 복잡도는 O(n × m)입니다. 따라서 배열의 크기가 매우 클 경우 결과 배열의 크기가 기하급수적으로 늘어날 수 있으니 주의해야 합니다.