[백트래킹] 조합, 순열, 중복조합, 중복순열 (재귀이용)

목차

1. 조합
2. 순열
3. 중복조합
4. 중복순열

들어가며 

백준에서 백트래킹 문제를 풀 때, 문제보고 대충 이런 식이면 되겠지 하고 문제들을 풀다 보니 헷갈리는 부분이 있었습니다. 

그동안 머릿속에 정리된 내용 없이 중구난방으로 문제를 풀었는데, 정리된 내용이 없나 하고 찾아보다가 얍문님의 블로그 포스팅을 보고 이거다 싶어서 하나로 정리해두려고 합니다. 

조합

조합이란?

서로 다른 n개의 원소를 가지는 어떤 집합에서 순서에 상관없이 r개의 원소를 선택하는 것을 의미합니다. 가장 중요한 것은 순서가 상관없다는 점입니다. 예를 들어 {1, 2, 3, 4, 5}로 이루어진 집합이 있을 때, 3개를 선택한다고 해봅시다. 이때 {1, 2, 3}과 {3, 2, 1}은 같은 부분집합입니다. 즉, {1, 2, 3} , {1, 2, 4}, {1, 2, 5}, {1, 3, 4},... 이런 식으로 나올 것입니다. (사진 참조)

조합 실행결과

이때 결과를 유심히 보면, 나오는 집합은 모두 정렬이 되어있는 것을 알 수 있습니다. 이것은 곧 시작점으로 사용된 요소는 뒤에서 한 번도 사용되지 않는다는 것을 의미합니다. 다시 말해, 시작점보다 작은 요소는 사용되지 않습니다. 예를 들어 {1, 2, 3} , {1, 2, 4}, {1, 2, 5}, {1, 3, 4},.. 와 같이 1이 시작점인 조합들이 쭉 나오고, 2가 시작점인 {2, 3, 4}, {2, 3, 5}, {2, 4, 5}에서는 1이 사용되지 않습니다. 이 성질을 이용하면 재귀방법으로 조합을 구현할 수 있습니다. 재귀함수의 매개변수 값으로 시작점 값을 전달해 주면, 호출받은 새 매개함수에서는 시작점 +1부터 반복을 시작하면 되니까 효율적으로 조합을 구할 수 있습니다.

//
//  Copyright (c) 2023 HyeJin Shin All rights reserved.
//조합
#include <iostream>
using namespace std;

#define MAX 5
int arr[MAX];
int ans[MAX];
bool visited[MAX];

void dfs(int cnt, int start){  //cnt는 현재 선택한 개수, start는 시작점
    if(cnt==3){ //하나의 경우의 수 충족
        for(int i=0;i<cnt;i++){
            cout<<ans[i]<<' ';
        }
        cout<<endl;
        return;  //이전 노드로 돌아감
    }
    else {
        for(int i=start;i<MAX;i++){
            ans[cnt]=arr[i];
            dfs(cnt+1,i+1); //그 다음 행 탐색
        }
    }
    return;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    arr[0]=1;
    arr[1]=2;
    arr[2]=3;
    arr[3]=4;
    arr[4]=5;
    
    dfs(0,0);
    
}

코드를 살펴보면, dfs함수 내에 재귀로 다음 함수를 호출하기 전에 dfs(cnt+1, i+1)로 시작점+1 한 값을 매개변수로 넘겨주어 다음 함수의 for문에서 시작점 +1부터 반복하게 구현했습니다. 

순열

순열이란?

서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관있게 선택하는 것을 순열(permutation)이라고 합니다. 가장 중요한 것은 순서가 다른 부분집합은 다른 집합이라는 것입니다. 앞의 예시와 동일하게 이번에도 {1, 2, 3, 4, 5}로 이루어진 집합이 있을 때, 3개를 선택한다고 해봅시다. 이때 {1, 2, 3}과 {3, 2, 1}은 다른 부분집합입니다. 즉, {1, 2, 3} , {1, 2, 4}, {1, 2, 5}, {1, 3, 2},... 이런 식으로 나올 것입니다. (사진 참조)

순열 실행결과 (길어서 뒷부분 생략)

이제 실행 결과는 조합과 달라졌습니다. 모든 결과가 정렬되어 나오던 조합과는 달리, {1, 3, 2}, {2, 1, 3}와 같은 정렬되지 않은 결과도 나오고 있는 것을 알 수 있습니다. 그러므로 시작점을 이용해서 재귀함수를 구하던 조합과 달리, 시작점을 없애고 모든 요소를 다 탐색해야 합니다. 하지만, 순열은 중복 순열과 다르기에 중복된 원소는 허용하지 않습니다. 따라서 방문체크를 하는 visited 배열을 만들어 방문한 적이 없는 요소만 재귀를 진행하도록 하면 순열을 구현할 수 있습니다. 

//
//  Copyright (c) 2023 HyeJin Shin All rights reserved.
//순열
#include <iostream>
using namespace std;

#define MAX 5
int arr[MAX];
int ans[MAX];
bool visited[MAX];

void dfs(int cnt){ //cnt는 현재 선택한 개수
    if(cnt==3){ //하나의 경우의 수 충족
        for(int i=0;i<cnt;i++){
            cout<<ans[i]<<' ';
        }
        cout<<endl;
        return;  //이전 노드로 돌아감
    }
    else {
        for(int i=0;i<MAX;i++){
            if(!visited[i]){
                ans[cnt]=arr[i];
                visited[i]=true;
                dfs(cnt+1); //그 다음 행 탐색
                visited[i]=false;
            }
        }
    }
    return;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    arr[0]=1;
    arr[1]=2;
    arr[2]=3;
    arr[3]=4;
    arr[4]=5;
    
    dfs(0);
    
}

코드를 살펴보면, 방문한 적이 없는 원소일 경우에만 dfs(cnt+1)로 다음 함수를 호출하게 했습니다. 이때 호출 전에 현재 원소의 방문체크를 해 준 뒤에, 재귀함수를 호출하면 현재 원소는 다시 중복되어 나오지 않을 것입니다. 또한 호출이 끝나고 돌아온 경우, 방문체크를 false로 다시 바꾸어주어 나중에 다른 재귀함수에서도 현재 원소를 사용할 수 있게 구현했습니다. (ex. {1, 2, 3}의 결과가 나온 후 1, 2, 3의 원소의 visited를 false로 바꾸어두어 나중에 {3, 2, 1}도 나올 수 있게 합니다.)

중복조합

중복조합이란?

서로 다른 n개에서 중복을 허용하여 r개를 택하는 조합을 의미합니다. 다른 것은 모두 조합과 같지만, 중복을 허용한다는 점이 중요합니다. 중복을 허용하기 때문에 {1, 1, 1}, {1, 1, 2}와 같은 원소의 중복은 허용되지만, 이미 {1, 1, 2}가 나왔다면, {2, 1, 1}은 다시 나올 수 없습니다. 

중복조합 실행결과 (길어서 뒷부분 생략)

따라서, 조합과 비슷하게 시작점 매개변수를 전달해 주면 앞에 시작점으로 사용된 원소가 다시 사용되는 것을 막을 수 있습니다. 하지만, 조합과 다른 점은 현재 시작점인 원소가 중복으로 사용될 수 있다는 점입니다. 

조합은 {2, 3, 4}, {2, 3, 5},... 와 같이 시작점 원소는 시작점에서 한 번 사용되지만, 중복조합은 {2, 2, 2}, {2, 2, 3}, {2, 2, 4},... 와 같이 시작점 원소는 중복으로 사용될 수 있습니다. 그러면 중복조합은 기존의 조합처럼 시작점을 재귀함수의 매개변수로 넘겨주되, 호출받은 새 매개함수에서는 시작점+1부터 탐색을 시작하는 것이 아닌, 시작점부터 반복을 시작하면 중복을 포함한 중복조합을 구할 수 있을 것입니다. (중복 조합은 조합의 성질을 따르기 때문에 절대 시작점보다 작은 수가 나올 수 없다는 점을 꼭 생각해야 합니다.)

//
//  Copyright (c) 2023 HyeJin Shin All rights reserved.
//중복조합
#include <iostream>
using namespace std;

#define MAX 5
int arr[MAX];
int ans[MAX];

void dfs(int cnt, int start){
    if(cnt==3){ //하나의 경우의 수 충족
        for(int i=0;i<cnt;i++){
            cout<<ans[i]<<' ';
        }
        cout<<endl;
        return;  //이전 노드로 돌아감
    }
    else {
        for(int i=start;i<MAX;i++){
            ans[cnt]=arr[i];
            dfs(cnt+1,i); //그 다음 행 탐색
        }
    }
    return;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    arr[0]=1;
    arr[1]=2;
    arr[2]=3;
    arr[3]=4;
    arr[4]=5;
    
    dfs(0,0);
    
}

코드를 살펴보면, dfs함수 내에 재귀로 다음 함수를 호출하기 전에 dfs(cnt+1, i)로 시작점 값을 매개변수로 넘겨주어 다음 함수의 for문에서 시작점부터 반복하게 구현했습니다. (시작점이 중복되어도 되기 때문입니다)

중복순열

중복순열이란?

중복 순열은 순열과 마찬가지로 n개 중에 r개를 순서에 상관있게 뽑는데, 중복을 허락하여 뽑는 것을 말합니다. 다른 것은 모두 순열과 같지만, 중복을 허용한다는 점이 중요합니다. 중복을 허용하는 순열이기 때문에 {1, 1, 1}, {1, 1, 2}, {1, 1, 3}와 같은 원소의 중복뿐만 아니라, {2, 1, 1}, {3, 1, 1}과 같이 이미 나왔던 결과도 순서가 다르다면 나올 수 있습니다. 

중복순열 실행결과 (길어서 뒷부분 생략)

순열과 모든 요소를 다 탐색해야 한다는 점은 동일하지만, 중복된 원소는 허용하기에 따로 방문체크를 할 필요가 없이 모든 원소를 탐색하면 됩니다.

//
//  Copyright (c) 2023 HyeJin Shin All rights reserved.
//중복순열
#include <iostream>
using namespace std;

#define MAX 5
int arr[MAX];
int ans[MAX];

void dfs(int cnt){
    if(cnt==3){ //하나의 경우의 수 충족
        for(int i=0;i<cnt;i++){
            cout<<ans[i]<<' ';
        }
        cout<<endl;
        return;  //이전 노드로 돌아감
    }
    else {
        for(int i=0;i<MAX;i++){
            ans[cnt]=arr[i];
            dfs(cnt+1); //그 다음 행 탐색
        }
    }
    return;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    arr[0]=1;
    arr[1]=2;
    arr[2]=3;
    arr[3]=4;
    arr[4]=5;
    
    dfs(0);
    
}

코드를 살펴보면, 순열 코드에서 방문체크 부분이 사라진 것을 알 수 있습니다.

참고 

더 자세한 설명은 얍문님을 참고하세요. 

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

[ 순열과 조합 구현 ] - 재귀를 통한 구현(2 - 순열) (C++)

[ 순열과 조합 구현 ] 재귀를 통한 구현(3 - 중복조합) (C++)

[ 순열과 조합 구현 ] 재귀를 통한 구현(4 - 중복순열) (C++)