[C++] 순열(Permutation) 조합(Combination) 알고리즘

 

백준에서 완전 탐색 문제를 풀다가

항상 조합과 순열을 만들 때 헷갈려서

아예 시간을 내어 정리하였다.

 

이 네 가지 알고리즘의 뼈대를 이해하면, 여러 방면에 쓰여서 좋은 거 같다.

 

이후 나오는 모든 코드의 n과 r은 다음과 같다. (n개 중에서 r개 선택)

#define n 4
#define r 3

 

1) 순열

순서를 따지고, 중복을 허용하지 않는다. (순서O, 중복X)

중복을 검사하기 위한 check 배열을 사용한다.

depth 를 하나씩 늘려가며, 배열에 하나씩 채우는 방법으로 재귀를 수행한다.

int pArr[r] = { 0, };
bool check[n + 1] = { false, }; 

void permutation(int depth){
    if(depth == r){
        printArray(pArr);
        return;
    }
    
    for(int i = 1; i <= n; i++){
        if(!check[i]){
            check[i] = true;
            pArr[depth] = i;
            permutation(depth + 1);
            check[i] = false;
        }
    }
}

int main(void){
    cout << "순열 (순서o, 중복x)" << endl;
    permutation(0);
    
    return 0;
}

(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ g++ permutation.cpp -o main.out
(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ ./main.out
순열 (순서o, 중복x)
1 2 3 
1 2 4 
1 3 2 
1 3 4 
1 4 2 
1 4 3 
2 1 3 
2 1 4 
2 3 1 
2 3 4 
2 4 1 
2 4 3 
3 1 2 
3 1 4 
3 2 1 
3 2 4 
3 4 1 
3 4 2 
4 1 2 
4 1 3 
4 2 1 
4 2 3 
4 3 1 
4 3 2 

 

2) 중복 순열

순서를 따지고, 중복을 허용한다. (순서O, 중복O)

중복 검사를 제외하면 위의 순열 코드와 동일하다.

int dpArr[r] = { 0, };

void duplicatePermutation(int depth){
    if(depth == r){
        printArray(dpArr);
        return;
    }

    for(int i = 1; i <= n; i++){
        dpArr[depth] = i;
        duplicatePermutation(depth + 1);
    }
}

int main(void){
    cout << "중복 순열 (순서o, 중복o)" << endl;
    duplicatePermutation(0);

    return 0;
}

(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ g++ permutation.cpp -o main.out
(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ ./main.out
중복 순열 (순서o, 중복o)
1 1 1 
1 1 2 
1 1 3 
1 1 4 
1 2 1 
1 2 2 
1 2 3 
1 2 4 
1 3 1 
1 3 2 
1 3 3 
1 3 4 
1 4 1 
1 4 2 
1 4 3 
1 4 4 
2 1 1 
2 1 2 
2 1 3 
2 1 4 
2 2 1 
2 2 2 
2 2 3 
2 2 4 
2 3 1 
2 3 2 
2 3 3 
2 3 4 
2 4 1 
2 4 2 
2 4 3 
2 4 4 
3 1 1 
3 1 2 
3 1 3 
3 1 4 
3 2 1 
3 2 2 
3 2 3 
3 2 4 
3 3 1 
3 3 2 
3 3 3 
3 3 4 
3 4 1 
3 4 2 
3 4 3 
3 4 4 
4 1 1 
4 1 2 
4 1 3 
4 1 4 
4 2 1 
4 2 2 
4 2 3 
4 2 4 
4 3 1 
4 3 2 
4 3 3 
4 3 4 
4 4 1 
4 4 2 
4 4 3 
4 4 4 

 

728x90

 

3) 조합

순서를 따지지 않고, 중복을 허용하지 않는다. (순서X, 중복X)

반복문을 돌며, 모든 경우에 대해 선택하는 것은 위의 경우들과 같다.

그러나, 반복문의 시작 값은 이전에 선택한 값 + 1이 된다.

int cArr[r] = { 0, };

void combination(int depth, int next){
    if(depth == r){
        printArray(cArr);
        return;
    }

    for(int i = next; i <= n; i++){
        cArr[depth] = i;
        combination(depth + 1, i + 1);
    }
}

int main(void){
    cout << "조합 (순서x, 중복x)" << endl;
    combination(0, 1);

    return 0;
}

(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ g++ combination.cpp -o main.out
(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ ./main.out
조합 (순서x, 중복x)
1 2 3 
1 2 4 
1 3 4 
2 3 4

 

4) 중복 조합

순서를 따지지 않고, 중복을 허용한다. (순서X, 중복O)

조합과 구현이 비슷하나,

반복문의 시작 값은 이전에 선택한 값이 된다.

int dcArr[r] = { 0, };

void duplicateCombination(int depth, int next){
    if(depth == r){
        printArray(dcArr);
        return;
    }

    for(int i = next; i <= n; i++){
        dcArr[depth] = i;
        duplicateCombination(depth + 1, i);
    }
}

int main(void){
    cout << "조합 (순서x, 중복o)" << endl;
    duplicateCombination(0, 1);

    return 0;
}

(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ g++ permutation.cpp -o main.out
(base) yunhongchan-ui-MacBook-Pro:week5 hongchanyun$ ./main.out
조합 (순서x, 중복o)
1 1 1 
1 1 2 
1 1 3 
1 1 4 
1 2 2 
1 2 3 
1 2 4 
1 3 3 
1 3 4 
1 4 4 
2 2 2 
2 2 3 
2 2 4 
2 3 3 
2 3 4 
2 4 4 
3 3 3 
3 3 4 
3 4 4 
4 4 4

 

 

 

익숙해졌다면, 아래의 문제들을 풀어보며 완전히 자기 것으로 만들어보자.

 

https://www.acmicpc.net/workbook/view/2052

문제집: N과 M (baekjoon)