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

이번 글은 저번 글에 이어서 순열에 대한 설명이다 !

( 저번 글 바로가기 )

기본적인 설명은 지난 글에서 모두 했으니 이번 글에서는 바로 순열 구현하는 것으로 들어가도록 하겠다.

[ 구현방법 ]

순열과 조합의 차이점은 순서가 있냐 없냐의 차이이다.

조합에는 순서가 없기 때문에, 과거에 시작점으로 삼았던 친구는 다시는 쳐다도 보지 말라는 식으로 설명을 했었다.

하지만, 순열은?? 과거에 시작점으로 삼았던 친구를 다시 한번 쳐다봐줘야 한다.

조합 → { 1, 2, 3 } = { 2, 1, 3 } 이므로, 시작점이 2가 되는 순간 더 작은 요소인 1은 쳐다도 보지 말아라 !

순열 → { 1, 2, 3 } != { 2, 1, 3 } 이므로, 시작점이 2가 되더라도 더 작은 요소인 1을 쳐다봐야 한다 !

라는 차이가 있다.

#include<iostream>
#include<vector>
 
#define MAX 5
using namespace std;
 
int Arr[MAX];
bool Select[MAX];
vector<int> V;
 
void Print()
{
    for (int i = 0; i < V.size(); i++)
    {
        cout << V[i] << " ";
    }
    cout << endl;
}
 
void DFS(int Cnt)
{
    if (Cnt == 3)
    {
        Print();
        return;
    }
 
    for (int i = 0; i < MAX; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(Arr[i]);
        DFS(Cnt + 1);
        V.pop_back();
        Select[i] = false;
    }
}
 
int main(void)
{
    Arr[0] = 1;
    Arr[1] = 2;
    Arr[2] = 3;
    Arr[3] = 4;
    Arr[4] = 5;
 
    DFS(0);
}

< 실행결과는 너무 많아서 짤랐음 ! >

위의 코드를 보면 조합과의 차이부터 한번 봐보자. 일단 DFS를 호출하는 매개변수의 갯수부터 다르다.

시작점을 결정해 주는 친구인 Idx 변수가 없어졌고, Cnt 혼자서만 매개변수로 사용되어지고 있다.

Idx가 없어진 이유는 위의 설명만으로도 충분히 알 수 있을 것이다. 시작점을 다시 한번 쳐다봐야 하기 때문이다 !

또 큰 차이점으로는 Vector가 하나 쓰이고 있다. 물론 이부분은 본인의 코딩스타일 , 코딩방식 이기 때문에 참고만 하자 !

조합에서는 Vector를 사용하지 않은 이유가, 0 ~ Max까지 반복하면서 Select[i] = true인, 즉, 선택당한 놈들이 나올 때 마다

출력을 해주면 그만이었지만, 순열은 그게 안되기 때문이다.

순열도 조합처럼 출력을 한다고 생각해보자. { 1, 2, 3}을 선택해서 출력을 할 것이고, {2, 1, 3}이 되는 순간

{1,2,3}과는 다른 놈이기 때문에 {2,1,3}도 출력을 할 것인데... 0부터 Max까지 반복하면서 Select[i] = true인 놈들을

출력해버리면, 당연히 1이 가장 먼저 있기 때문에 {1,2,3}이 또 출력되게 될 것이다. 따라서 본인은 Vector를 사용해서

선택할 때마다, Vector에 넣어주고 빼주면서 Vector를 출력하는 방식으로 구현을 한다.

구체적으로 알아보자. DFS의 재귀 과정을 한번 알아보도록 하자 !

[ 현재 Cnt = 0 ]

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

2. Vector에 0번째 값인 '1' 을 넣겠습니다.

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

   [ 현재 Cnt = 1 ] ★

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

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

   3. Vector에 1번째 값인 '2'를 넣겠습니다.

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

      [ 현재 Cnt = 2 ]

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

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

       3. Vector에 2번째 값인 '3'을 넣겠습니다.

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

         [ 현재 Cnt = 3 ]

         1. Cnt 가 3이 되었습니다. 원하는 과정을 진행후 Return 시키겠습니다.

이렇게 {1,2,3 } 이 출력되어진다. 사실 여기까지는 조합과 똑같기 때문에 설명이 크게 의미가 없다.

그렇다면 {1,2,5} 까지 뽑고 return 된 상태까지 왔다고 생각해보자.

지금 무슨 상황일까?? 음... 아마도 [ 현재 Cnt = 1 ] (위의 별표) 로 돌아가게 될 것이다.

{1,2,5} 까지 뽑는게, ★에서 1번째 값인 2를 선택하고, 재귀를 호출하면서 그 안에서 모두 일어난 일이다. 즉, 그 일들을

다 끝내고, 다시 ★로 온 것이다. (코드를 보면서 잘 생각하자 놓치지 말고 ! )

그렇다면, 이제는 재귀 밑에 내용을 실행할 차례이다. 현재 i값은 1이다.

V.pop_back() 선택했던 1번째 값을 벡터에서 빼내겠습니다. 그리고 선택했던 값을 선택 취소하겠습니다. 를 진행하고

i가 ++되어, 2가 될 것이다. (생각을 하자 생각을..)

[ 현재 Cnt = 1, i = 2 ]

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

2. Vector에 2번째 값인 '3'을 넣겠습니다.

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

    [ 현재 Cnt = 2 ]

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

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

     3. Vector에 1번째 값인 '2'를 넣겠습니다.

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

       [ 현재 Cnt = 3 ]

        1. Cnt가 3이 되었습니다. 원하는 과정을 진행후 Return 시키겠습니다.

그렇다면 지금 우리가 선택한 숫자는 ?? { 1, 2, 3 } 인데... 순서를 보면 벡터에 {1, 3, 2} 순서로 저장되어있다.

이렇게 순열이 출력되는 것이다.

(1)편에서도 말했지만, 이 재귀가 돌아가는 것을 모두 다 이해하기에는 너무나도 복잡하다. 하지만 위에 설명만 잘 이해했고

어떻게 돌아가는지 정도만 알고 있다면, 앞으로 순열과 조합 문제를 구현하는데에는 크게 어려움이 없을 것이라고 생각한다.

너무나도 기본적이고 많이 쓰이는 알고리즘이다 ! 꼭 알아두도록 하자 !