조합 (Combination)

- 조합 (Combination) -

 

n개의 수를 중복을 허용하지 않고(start)

r개를 순서 상관없이 나열할 수 있는 모든 경우의 수 (1 ≤ r ≤ n)

 

---

 

문제인식)

0부터 9(n)까지의 수가 있다.
이들을 이용하여 4(r)개의 수를 중복없이, 순서 상관없이 나열하고자 할 때
가능한 모든 경우를 각각 한 줄씩 출력하고자 한다면 어떻게 해야할까?

int n=9, r=4;

 

해결과정)

1) 출력에 이용할 배열(a[4])을 준비한다.
2) 함수의 인수를 idx, start로 설정한다.

idx는 a배열에 재귀진입하기위한 인덱스,

start는 중복방지와 오름차순을 위한 시작점이다.

 

만약 1, 2, 3, 4의 네 수를 순열로 처리한다면... (이 경우, n=4, r=4, start=1인 셈)

"1 2 3 4"
"1 2 4 3"
.
.
.

의 출력이 이뤄지게 된다.

 

그러나 조합으로 처리하려면 위 예시의 두번째 라인처럼

순서역전이 발생한다.(조합에서는 허용되지 않아야 할 경우)

 

이를 방지하고자 a[3]에는 4부터 삽입을 시작하도록 해야한다.

마찬가지로 a[2]에는 3부터 삽입을 시작해야 한다.

이렇게 하면 두번째 라인처럼 a[3]에 3이 다시 들어갈 일도 없고,

중복또한 방지되며, 자연스레 오름차순으로 출력할 것이다.

 

3) idx에 시작점(start)부터 n까지 삽입하는 반복문을 시작한다.

4) 다음 인덱스(idx+1)의 삽입 시작점은 이전에 쓰였던 수(i)보다 하나 더 큰 수로 설정한다.(start=i+1)

 

 

(※ [더보기]를 클릭하면 C/C++ 소스코드를 참조할 수 있습니다.)

#include<cstdio>

int n=9, r=4;
int a[4];

void Combination(int idx, int start) {
    if(idx>=r) {
        //출력
        for(int i=0; i<r; i++) printf("%d ", a[i]); printf("\n");
        //종료
        return;
    }

    for(int i=start; i<=n; i++) {
        a[idx]=i;
        Combination(idx+1, i+1);
    }
}

int main() {
    Combination(0, 0);

    return 0;
}

해당 소스코드를 컴파일, 실행하면
각 줄마다 조합의 경우가 하나씩 오름차순으로 출력하게 된다.

위 코드의 경우 시간복잡도는 당연히 O(n의 r제곱)이다.

 

응용)

백준 문제 - N과 M (2)

 

내림차순으로 출력해보기

 

출력용 배열대신 벡터에 push, pop하는 방식으로 해보기(start를 이용하는 원리는 같다.)

(※ [더보기]를 클릭하면 C/C++ 소스코드를 참조할 수 있습니다.)

#include<cstdio>
#include<vector>
using namespace std;

int n=9, r=4;
vector<int> v;

void Combination(int start) {
    if(v.size()>=r) {
        //출력
        for(int i=0; i<r; i++) printf("%d ", v[i]); printf("\n");
        //종료
        return;
    }

    for(int i=start; i<=n; i++) {
        v.push_back(i);
        Combination(i+1);
        v.pop_back();
    }
}

int main() {
    Combination(0);

    return 0;
}

 

등