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

브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는

결과 값을 찾는 방식이다.

이 글에서는, 순열과 조합을 STL을 사용하지 않고, 재귀를 통해서 구현하는 방법에 대해서 설명해보고자 한다.

개념부터 차례차례 알아보도록 하자 !

[ 순열 ? 조합 ? ]

- 순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다.

  말 그대로, 순서가 존재하는 열 이라는 것이다.

  즉 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } 등.. 모두 다른 결과를 가져온다. 순서가 다르기 때문이다.

 

  조합은 순서가 상관이 없는 모임을 의미한다. 순서가 상관 없기 때문에

  { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은것으로 취급을 한다. 순서가 상관없기 때문에

  1, 2, 3 이라는 3개의 숫자로 이루어져있다는 점에서 똑같은 취급을 하는 것이 조합이다.

 

  (사실, 인터넷 검색 한번도 안해보고 본인이 아는 선에서 써놓은 개념이라서 수학적으로 정확하지는 않습니다 !)

[ 구현방법 ]

사실, next_permutation / prev_permutation과 같은 순열과 조합을 구현하는 함수를 STL을 통해서 쉽게 구현할 수

있다. 하지만, 지금 이 글에서는 STL을 사용하는 것이 아닌 재귀를 통해서 구현하는 방법에 대해서 알아보자.

지금부터 여러가지 코드와 설명을 보게 될 텐데, 모든 내용은 "5개 중에 3개 뽑기" 로 설명을 하겠다.

먼저 조합에 대해서 알아보자.

{ 1, 2, 3, 4, 5 } 5개의 숫자 중에서 순서와 상관없이 3개의 숫자를 뽑으세요 ! 가 문제이다.

일단 대충 적어보자면 { 1, 2, 3 }, {1, 2, 4, }, {1, 2, 5} ... , {2, 3, 4 }, {2, 3, 5}, ...... {3, 4, 5} 이런식으로 쭉 나올것이다.

재귀로 조합을 구현할 때에는, 시작점을 결정한 이후, 그 전의 요소는 다시는 쳐다도 안본다는 것이 중요하다.

물론 이 말은 본인이 쉽게 설명하고 본인이 받아들인대로 설명을 하다보니 이런 말이 나온 것이다....

처음에는 시작점이 1일 것이다. {1, 2, 3} .... {1, 4, 5} 까지 쭉 나오고 이 다음에 시작점이 2가 될 것이다.

{2, 3, 4}, {2, 3, 5}...  여기서 보면.. 시작점이 2가 되는 순간, 1은 쳐다도 보지 않는다. 왜냐하면, 1이 들어가는 순간 이미

선택해놓은 조합이기 때문이다. 이게 무슨 말일까 ?

{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5} 이게 1을 시작점으로 삼고 나올 수 있는 모든 조합이다.

그렇다면 이제는 시작점을 2로 잡아보자.

{2,1,3},{2,1,4},{2,1,5},{2,3,4,},{2,3,5},{2,4,5} 이게 2를 시작점으로 잡고 나올 수 있는 모든 조합이다.

여기서, 위에 밑줄 그어 놓은 3개를 잘 봐보자... 저게 처음 나온 조합일까? 아니다.

{2,1,3} = {1,2,3}

{2,1,4} = {1,2,4}

{2,1,5} = {1,2,5} 로 이미 시작점이 1일 때 나온 조합들이다. 위에서 말했다 시피, 조합은 순서과 상관없기 때문에

같은 것으로 본다. 즉, 시작점이 무조건 가장 처음인 0부터 시작하는 것이 아니다 정도만 알고 코드를 확인해보자.

조합을 구현할 때, 하나의 시작점을 정한다면, 그 시작점 이전에 나온 원소들을 다시 쳐다보지 말자 !

#include<iostream>
 
#define MAX 5
using namespace std;
 
int Arr[MAX];
bool Select[MAX];
 
void Print()
{
    for (int i = 0; i < MAX; i++)
    {
        if (Select[i] == true)
        {
            cout << Arr[i] << " ";
        }
    }
    cout << endl;
 
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == 3)
    {
        Print();
        return;
    }
 
    for (int i = Idx; i < MAX; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;

        DFS(i, Cnt + 1);
        Select[i] = false;
    }
}
 
int main(void)
{
    Arr[0] = 1;
    Arr[1] = 2;
    Arr[2] = 3;
    Arr[3] = 4;
    Arr[4] = 5;
 
    DFS(0, 0);
}

위의 코드가 조합을 구하는 코드이다. (5개 중에 3개 뽑기)

핵심은 DFS(int Idx, int Cnt) 함수이다. 이 함수의 재귀를 통해서 모두 구하게 된다.

먼저 사용한 배열들에 대해서 보자. Arr[] 배열이 있고, Select[] 라는 배열이 있다.

Arr[] 배열은 그냥 우리가 입력하는 숫자들을 저장하는 변수들이다. 저 배열에 들어있는 값들 중 3개를 뽑는 것이다.

Select[] 배열이 굉장히 중요하다. 이 배열의 역할은 이미 선택한 숫자라면 선택하지 않고, 선택하지 않은 숫자라면

선택할 수 있음을 표시해주는 배열이다.

Select배열의 역할이 중요한 이유는, 우리가 현재 구하고자 하는 것인 "중복을 허용하는 뽑기가 아니기 때문" 이다.

반대로, 이후에 나오는 '중복순열', '중복조합' 글에서 보면 알겠지만, 중복을 허용하는 수열을 구하는 과정에서는 Select배열이 사용되지 않는다. 하지만, 지금 우리는 중복을 허용하지 않는 수열을 구하는 과정이다.

따라서, Select배열을 통해서 어떤 값이 이미 뽑혔는지, 반대로 어떤 값이 아직 뽑히지 않았는지에 대해서 판단을 해주어야 한다.

Select[] 배열을 선언하고, 이 배열을 통해서 중복을 허용하지 않도록 만들어주자 !

조합을 구하는 함수에는 보통 2개의 매개변수가 들어간다. 위의 코드에서 보면 int Idx, int Cnt 이렇게 2개의 변수가

들어가져있다. 여기서 Idx가 위에서 계속 말한 시작점을 결정해주는 변수이고, Cnt는 몇 개를 뽑아야 하는지,

우리가 원하는 갯수만큼 뽑았는지를 판단하는 변수이다.

구체적으로 알아보자.

[ Idx변수 - 시작점을 결정하는 친구구나 ! ]

Idx가 사용되는 for문부터 천천히 알아보자.

보면 for(int i = Idx; i < Max; i++) 라고 되어있다. 초심으로 돌아가보자. 이 문구의 의미는

"i 라는 int형 변수는 Idx라는 값에서 시작하여서 1씩 증가하면서 Max까지 반복합니다." 가 된다.

그 안에 내용을 말 그대로 풀어쓰자면

"i번째 값을 선택 했으면 그냥 지나가세요. 선택하지 않았다면 선택했다고 표시해주고, 재귀호출을 하겠습니다.

 그리고 다시 선택하지 않았다고 표시해줄게요" 가 된다. 여기까지만 일단 알아놓자.

[ Cnt변수 - 우리가 몇개를 골랐는지 알려주는 친구구나 ! ]

Cnt변수가 사용된 if문부터 보자.

if(Cnt == 3) 이라고 되어있다. 사실 3이 아니여도 된다. 본인은 지금 5개 중에 3개를 선택하기 때문에 3을 적어놨을 뿐,

저 값은 우리가 골라야 하는 갯수를 적어주면 된다.

우리가 원하는 만큼 골랐다면, 그 이후 하려는 작업을 진행해주면 된다

조합을 구현할 때에는 2개의 매개변수를 이용해서 구현할 수 있다.

1. Idx변수 : 시작점을 결정해주는 변수이다. 우리는 Idx를 시작점으로 삼는 순간, Idx이전에 나온 원소는 쳐다도

   보지 않을 것이다.

2. Cnt변수 : 우리가 현재 뽑은 원소의 갯수를 결정해주는 변수이다. 현재 뽑은 원소의 갯수가 우리가 최종적으로

   뽑고자 하는 원소의 갯수와 일치한다면, 그 다음 프로세스를 진행하면 된다.

위의 설명을 토대로 { 1, 2, 3 } 이라는 조합이 나오는 과정을 알아보자. 처음에는 선택되지 않았기 때문에 초기 Select배열의

모든 값들은 false일 것이다.

( 여기서 주의해야 될게 Select[a] 는 a라는 숫자가 선택됬고 안됬고를 의미하는것이 아닌, a번째 값이 선택됬고 안됬고를

  의미하는 것이다. Select[0] = true 의 의미는 숫자 0이 선택됬음을 의미하는것이 아니라, 0번째 값인 Arr[0] = 1이 선택되었

  고 안되었고를 의미하는 것 ! )

DFS(0, 0)이 호출되면서 Cnt == 3이 아니기 떄문에 밑에 for문으로 들어갈 것이다.

- [ 현재 Idx = 0 , Cnt = 0 ]

  1. 0번째 값이 선택되지 않았으므로, 선택하겠습니다.

  2. 재귀를 호출하겠습니다.

    [ 현재 Idx = 0 , Cnt = 1 ]

    1. 0번째 값이 선택되었으므로 지나가겠습니다.

    2. 1번째 값이 선택되지 않았으므로, 선택하겠습니다.

    3. 재귀를 호출하겠습니다.

     [ 현재 Idx = 1, Cnt = 2 ]

      1. 1번쨰 값이 선택되었으므로 지나가겠습니다.

     2. 2번째 값이 선택되지 않았으므로, 선택하겠습니다.

     3. 재귀를 호출하겠습니다. ★

      [ 현재 Idx = 2, Cnt = 3 ]

       1. Cnt가 3개가 되었습니다. 원하는 작업을 진행하고 return 시키겠습니다.

우리는 지금 0번째값, 1번째값, 2번째 값을 선택했다. 따라서, {1, 2, 3} 이 나오게 되는 것이다.

이후 과정도 한번 살펴보자. return하면 어떻게 될까??

[ 현재 Idx = 2, Cnt = 3 ] 인 함수가 끝나고, [ 현재 Idx = 1, Cnt = 2 ] 인 함수로 들어가게 될 것이다. 이 함수에 남아있는 작업이 뭐가있을까?? 2번째 값을 선택했고, 재귀를 호출했고 그 다음은 2번째 값을 선택하지 않는 것이다. 이 후, for문이 계속 실행될 것 이다. 계속 해보자.

[ 현재 Idx = 1, Cnt = 2 ]

1. 1번째 값이 선택되었으므로 지나가겠습니다.

2. 2번째 값이 선택되지 않았으므로, 선택하겠습니다.

3. 재귀를 호출하겠습니다. ★ ( 여기로 돌아왔음 )

4. 2번째 값을 선택하지 않겠습니다.

5. i값이 ++ 되어 i = 3이 되었습니다.

6. 3번째 값이 선택되지 않았으므로 선택하겠습니다.

7. 재귀를 호출하겠습니다.

  [ 현재 Idx = 3 , Cnt = 3 ]

  1. Cnt가 3개가 되었습니다. 원하는 작업을 진행하고 return 시키겠습니다.

우리는 지금 0번째값, 1번째값, 3번째 값을 선택했다. 따라서, {1, 2, 4} 가 나오게 되는 것이다.

이런식으로 계속 반복된다면??? 모든 조합에 대한 경우를 모두 고를 것이다.

여기서 다시한번 Idx에 대해서 되새겨보자.

위에 글에서 본인이 써놓은 [ 현재 Idx = ~ , Cnt = ~ ] 라고 써놓은 내용에서 보면

Idx보다 작은 원소들을 쳐다 보는지 한번 확인해보자.

예를 들어 Idx = 1 일 때를 보면, 0 번째 값에 대한 이야기조차 하는지?

Idx = 2일 때를 보면, 0번째 , 1번째 값에 대해 이야기를 하는지?

아마 쳐다도 안본다는 것을 알 수 있을 것이다.

즉 5개(1,2,3,4,5) 중에 3개를 뽑는다면...

제일 먼저 1을 뽑아 !, 그 다음 원소로 뽑을 것을 결정해 ! 2를 뽑았으면 1, 2는 쳐다보지 말고

3,4,5 중에서 고른다 !

1 다음에 3을 뽑았다 ? 그럼 3보다 작은 원소인 1,2 는 쳐다도 보지말고 4, 5 중에서만 골라 !

이런식으로 구현되는 것이다.

이 재귀과정을 그림으로 나타내보면 보다 수월하게 이해할 수 있다.

.

정말 간략하게, DFS함수가 [ Idx = 0 , Cnt = 0 ] 부터 , [ Idx = 2 , Cnt = 3 ] 이 될 때까지 호출 과정을 그림으로

표현한 것이다. 가장 처음 검정색 사각형으로, (0 , 0)이 호출되고, 그 다음과정으로는 for문 안에서 (0 , 1)이 호출되어 진다.

이런식으로 반복하다가 (2 , 3)으로 DFS함수가 호출되었다고 생각해보자. 그럼, 우리가 뽑고자 하는 원소의 갯수가 3개이고,

현재 뽑은 원소의 갯수를 알려주는 Cnt변수가 3이기 때문에 우리는 가장 위에 있는 조건문에 의해서 DFS 함수가 종료된다는 것을 알 수 있다. 그럼 종료되면 그 다음 어디로 가게될까 ?? 종료된다면 그 다음 Idx , Cnt의 상태는 어떻게 될까 ??

이런 부분을 위의 그림에서 [ Idx = 2 , Cnt = 3 ] 이 종료되면 어디로 가는지 쉽게 파악할 수 있다.

위에 그림에서 보듯이, 노랑색 사각형인 [ Idx = 2 , Cnt = 3 ] 이 종료된다면 , 그 다음 사각형인 빨강색 사각형, 즉,

[ Idx = 1 , Cnt = 2 ] 로 돌아간다는 것을 확인할 수 있다.

재귀로 조합, 순열, 중복조합, 중복순열을 구하는 과정은 위와 같이 재귀 안에서 재귀로 파고드는 형태로 구현되어 있다.

그래서 그 형태가 이해하기에 약간 복잡할 수 있지만, 본인처럼 위의 그림을 직접 그려보면서 이해해보려 한다면, 이해할 수 있을 것이다.

이게 조합을 구현하는 기본적인 방식이다. 

사실 본인도 저 재귀가 끝까지 어떻게 돌아가는지에 대해서는 약간 받아들인 경향도 있다. 재귀가 계속 일어나다 보니

굉장히 헷갈리기도 하고 사람이 계산하기에는 어려운 부분이 있기 때문이다.

하지만, 기본적인 재귀 순환방식과 Idx, Cnt값에 따라서 원하는 조합을 구하는데는 지금까지 문제없이 모두 잘 구현하고

있다.

알고리즘 분야에서 정말 많이쓰이기도 하면서 정말 기본적인 내용이니 꼭 알아두도록 하자 !

2편에서는 순열에 대해서 !....