[Algorithm] 조합 (Combination)

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

오늘은 조합에 대해 알아보도록 하겠습니다.

 

 

조합 (Combination)

조합이란, 요소의 개수가 n개인 집합에서 r개를 순서 없이 뽑는 것을 말합니다. 보통 조합은 $_{n}C_{r}$으로 표현하며, 다음과 같이 정의됩니다.

$$_{n}C_{r} = \frac{n!}{r!(n-r)!}$$

또한, 조합은 또다른 공식이 있는데, 다음과 같습니다.

$$_{n}C_{r} = _{n-1}C_{r-1} + _{n-1}C_{r}$$

이해가 잘 안되시죠? 간단히 예를 들어보겠습니다.

[1, 2, 3]에서 2개를 뽑는다고 가정해봅시다. 그러면 다음과 같이 두 가지 경우로 나눌 수 있습니다.

• (1, x) : 첫번째 요소를 1로 결정한 경우. 즉, $_{n-1}C_{r-1}$에 해당함.
• (y, z) : 아무 요소도 결정하지 못한 경우. 즉, $_{n-1}C_{r}$에 해당함.

(1, x)는 (1, 2)와 (1, 3)이 되며, (y, z)는 (2, 3)이 됩니다.

위 점화식을 이용해서 재귀로 조합을 구현할 수 있습니다.

 

 

재귀 코드 (javascript)

위 점화식을 이용한 combination함수는 다음과 같습니다.

function combination(source, target, n, r, count) {
    if(r === 0)final.push(target);
    else if(n === 0 || n < r) return;
    else {
        target.push(source[count]);
        combination(source, Object.assign([], target), n - 1, r - 1, count + 1);
        target.pop();
        combination(source, Object.assign([], target), n - 1, r, count + 1);
    }
}

const source = [1, 2, 3, 4, 5];
const final = [];

combination(source, [], 3, 2, 0);
console.log('final', final);
// 출력
// final [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]

위 코드에서 중요한 점은 다음과 같습니다.

• r이 0일때 조합의 경우의 수 중 하나를 결과에 추가한다.
• n이 0이거나 r이 n보다 큰 경우, 아무것도 안한다. (noop)
• $_{n-1}C_{r-1}$을 호출하기 전에 요소 하나를 선택한다.
• $_{n-1}C_{r}$을 호출하기 전에 요소 하나를 뺀다.
• 재귀 호출시, target을 깊은 복사한다.

호출 순서는 다음과 같습니다.

아 참고로 맨 처음엔 $_{n}C_{2}$가 아니라 $_{3}C_{2}$입니다...

 

 

반복 코드 (javascript)

반면에 반복을 이용한 조합은 매우 간단합니다.

for(let i = 0; i < source.length; i++) {
    for(let j = i; j < source.length; j++) {
        // r의 값만큼 for문이 중첩되어야 합니다.
        final.push([source[i], source[j]]);
    }
}

다만, r이 증가하면 증가할수록 어마어마한 for문 지옥이 펼쳐지며, 시간복잡도도 기하급수적으로 늘어납니다.