[C++] 순열(Permutation)과 조합(Combination)

순열과 조합

순열과 조합을 구하는 알고리즘은 코딩테스트에서 단독으로 출제되는 경우가 많지는 않지만 bfs, dfs처럼 시뮬레이션 유형에서 풀이를 위해 사용되는 경우가 많습니다.

 

그렇게 자주 쓰이지는 않지만 종종 등장하고, 모르면 풀지못하는데 한동안 안쓰다 보면 시험장에서는 까먹는 경우가 많습니다. 원리를 이해하고 있으면 몇번의 시행착오를 거쳐서 구현하고 사용 할 수 있지만 그때마다 '아 바로 기억 났으면 시간 훨씬 아꼈을텐데' 하는 생각은 많은 아쉬움을 남기곤 합니다.

때문에 이번 기회에 순열과 조합을 정리하고 넘어가려고 합니다.

 

순열과 조합을 구하는 알고리즘이 재귀와 백트래킹이 활용되는 대표적인 예시인 만큼 두가지에 대한 이해가 부족하면 조금 어렵게 느껴지실 수 있으니 혹 모르신다면 숙지하고 오시는 것을 추천드립니다!

 

수학에서의 순열과 조합을 나타낼 때 nPr, nCr과 같은 표현이 쓰이기 때문에 알고리즘 구현시에도 n 과 r을 사용하였습니다. 또한 수학적으로 순열과 조합이 무엇인지 이해하고 계실거라고 생각하겠습니다!.

 

순열

순열을 n개 중에서 r개를 중복 없이, 순서를 따져서 고르는 경우의 수 입니다.

때문에 중복을 검사하기 위한 check 배열이 하나 필요합니다.

순열이 저장될 배열에 인덱스로 사용할 depth가 되는 k 값을 하나씩 늘려가면서 배열을 채웁니다.

재귀를 탈출하는 조건은 k가 r과 같아질 때 입니다.

void permutation(int k)
{
    if(k == r)
    {
        for(int i = 0; i < n; i++)
        {
            cout << arr[i] << " ";
        }cout << "\n";
        return;
    }

    for(int i = 1; i <= 3; i++)
    {
        if(!check[i])
        {
            check[i] = 1;
            arr[k] = i;
            permutation(k+1);
            check[i] = 0;
        }
    }
}

 

중복 순열

순서가 있다는 점은 순열과 동일하지만 중복을 허용합니다.

이 때문에 중복 검사를 위해 사용하는 check 배열을 이용하지 않는다는 점을 제외하면 순열과 동일합니다.

중복순열이 영어로 permutation with repetition이라 함수명을 permutation_rep로 하였습니다.

void permutation_rep(int k)
{
    if(k == r)
    {
        for(int i = 0; i < n; i++)
        {
            cout << arr[i] << " ";
        }cout << "\n";
        return;
    }

    for(int i = 1; i <= 3; i++)
    {
        arr[k] = i;
        permutation_rep(k+1);
    }
}

 

조합

조합은 n 개중 r 개를 순서 없이, 중복 없이 뽑는 경우입니다.

중복이 없기 때문에 순열과 마찬가지로 check 배열을 사용하여 중복 검사를 하지 않을까 싶겠지만 사용하지 않습니다.

순열과 다르게 순서가 없기 때문에 반복문의 시작점을 변경해 주어야합니다. 이 때 시작점을 이전에 선택한 값 + 1 을 해주면 자연스럽게 중복제거가 이루어집니다.

void combination(int k, int idx)
{
    if(k == r)
    {
        for(int i = 0; i < 2; i++)
        {
            cout << arr[i] << " ";
        }cout << "\n";
        return;
    }

    for(int i = idx; i <= n; i++)
    {
        arr[k] = i;
        combination(k + 1, i + 1);
    }
}

 

중복 조합

순열과 중복 순열의 관계처럼 중복 조합 또한 조합에서 중복 검사만 제거하면 됩니다.

조합을 구현할 때 중복을 제거한 방식이 이전에 선택한 값 + 1을 시작점으로 이용한 것이기 때문에 시작점을 이전에 선택한 값 으로 하면 자연스럽게 중복 조합이 구현됩니다. 

void combination_rep(int k, int idx)
{
    if(k == r)
    {
        for(int i = 0; i < 2; i++)
        {
            cout << arr[i] << " ";
        }cout << "\n";
        return;
    }

    for(int i = idx; i <= n; i++)
    {
        arr[k] = i;
        combination(k + 1, i);
    }
}

 

 

https://github.com/dsaf2007/baekjoon/blob/main/cpp/practice/combination.cpp

 

순열과 조합이 모두 구현되어있는 전체 코드입니다. 실행하셔서 결과를 확인하실 수 있습니다.

 

자주 안쓰면 헷갈리는 순열과 조합을 정리해 보았습니다.

C++ 에는 다른 언어에는 없는 next_permutation과 prev_permutation이 존재합니다. 이를 이용해서 순열과 조합을 구하는 방법이 있지만 저는 개인적으로는 재귀를 통해 구현하는것을 우선 알고있어야 한다고 생각합니다. 다음번에는 next_permutation과 prev_permutation을 다뤄보도록 하겠습니다.