[Algorithm] 조합(nCr)의 모든 경우를 구하는 방법(c++, javascript)

이 글은 n개의 수 중 r개를 고르는 모든 경우(조합)를 구하는 방법에 대해 설명한다.

조합

서로 다른 N개의 원소를 순서 없이 골라낸 것을 조합(combination)이라고 부른다.

모든 조합 만들기

중첩 반복문

0번부터 차례로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드를 작성해보자.

예를 들어, n이 7이라면 (0, 1, 2, 3) (0, 1, 2, 4) (0, 1, 2, 5) ... (3, 4, 5, 6)의 모든 경우를 출력하면 된다.

이를 간단하게 푸는 방법에는 다음과 같은 4중 for문이 있다.

//c++
for(int i=0; i<n; i++){
	for(int j=i+1; j<n; j++){
    	for(int k=j+1; k<n; k++){
        	for(int l=k+1; l<n; l++){
            	cout << i << " " << j << " " << k << " " << l << endl;
            }
        }
    }
}

//javascript
for(let i=0; i<n; i++){
	for(let j=i+1; j<n; j++){
    	for(let k=j+1; k<n; k++){
        	for(let l=k+1; l<n; l++){
            	console.log(`${i} ${j} ${k} ${l}`);
            }
        }
    }
}

만약 네 개가 아니라 다섯 개를 골라야 한다면 5중 for문을, 여섯 개를 골라야 한다면 6중 for문을 쓰면 된다.

위와 같은 중첩 for문은 골라야 할 원소의 수가 늘어날수록 코드가 길고 복잡해지는데다, 골라야 할 원소의 수가 입력에 따라 달라질 수 있는 경우에는 사용할 수 없다는 문제가 있다.

재귀 호출

재귀 호출은 이런 경우에 단순한 반복문보다 간결하고 유연한 코드를 작성할 수 있도록 해준다. 위 작업을 네 개의 조각으로 나누어 각 조각에서 하나의 원소를 고르게 구현할 수도 있다. 원소를 고른 뒤, 남은 원소들을 고르는 작업을 떠넘기는 재귀 함수를 작성하면 된다.

이때 남은 원소들을 고르는 작업을 다음과 같은 입력들의 집합으로 정의할 수 있다.

• 원소들의 총 개수
• 더 골라야 할 원소들의 개수
• 지금까지 고른 원소들의 번호

//n: 전체 원소의 수
//picked: 지금까지 고른 원소들의 번호를 담는 배열
//toPick: 더 고를 원소의 수

//c++

void pick(int n, vector<int>& picked, int toPick){
	//기저 사례: 더 고를 원소가 없을 때 고른 원소들을 출력
    if(toPick==0){
    	printPicked(picked); return;
    }
    //고를 수 있는 가장 작은 번호를 계산
    int smallest = picked.empty()? 0 : picked.back()+1;
    //원소 하나를 고르고 나머지 원소를 고르는 작업은 재귀호출로 해결
    for(int next=smallest; next<n; next++){
    	picked.push_back(next);
        pick(n, picked, toPick-1);
        picked.pop_back();
    }
}

//javascript
const pick = (n, picked, toPick) => {
	if(toPick===0){
    	console.log(picked.join(" "));
    	return;
    }
    //picked가 빈 배열일 때는 0, 아닐 때에는 마지막 원소+1;
    const smallest = picked.length && picked[picked.length-1]+1;
    for(let next=smallest; next<n; next++){
    	picked.push(next);
        picked(n, picked, toPick-1);
        picked.pop();
    }
};

이 코드는 텅 빈 답에서 시작해서 매 단계마다 하나의 원소를 추가하는 일을 반복하다가, 하나의 답을 만든 뒤에는 이전으로 돌아가 다른 원소를 추가하는 식으로 모든 답을 생성한다.

중첩 for문과 달리 n개의 원소 중 몇 개를 고르든지 사용할 수 있다는 장점이 있다.