[Algorithm / C++] BackTracking 기법을 활용한 순열(Permutation)과 조합(Combination) 구현

Development/Algorithm

[Algorithm / C++] BackTracking 기법을 활용한 순열(Permutation)과 조합(Combination) 구현

blog post

순열과 조합

개발 과정에서 어떤 집합의 경우의 수를 찾아야 하는 경우가 종종 있습니다. 이때 경우에 따라 조합 혹은 순열을 활용해야 하는데, 둘의 차이는 다음과 같습니다.

- 조합(Combination): 순서 바뀜 허용 안함. 중복 허용 안함. 표현: nCr = n! / r! * (n - r)! .

- 순열(Permutation): 순서 바뀜 허용. 중복 허용 안함. 표현: nPr = nCr x r! .

예를 들어 {1,2,3} 세개의 요소를 가지고 있는 벡터 v={1,2,3} 를 활용하여 각각 순열과 조합을 구성하고자 하는 경우 아래와 같은 경우의 수를 도출할 수 있습니다.

순열:

- 3개의 원소로 조합 가능한 모든 구성: 3P3 (nPn = n!). 가능한 구성: {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

- 3개의 원소에서 2개의 순열 구성: 3P2. 가능한 구성: {1,2}, {2,1}, {2,3}, {3,2}, {3,1}, {1,3}

조합:

- 3개의 원소에서 2개의 조합 구성: 3C2. 가능한 구성: {1,2}, {2,3}, {3,1}

- 3개의 원소에서 3개의 조합 구성: 3C3 (nCn = 1). 가능한 구성: {1,2,3}

(본 포스팅에서는 중복 순열과 중복 조합에 대해서는 다루지 않겠습니다)

BackTracking (백트래킹)

백트래킹은 특정 조건을 만족하는 결과 값을 찾을 때까지 탐색하는 일종의 탐색 기법입니다. 알고리즘에서 경우의 수를 탐색하는 과정에서 많이 쓰이는데, '백트래킹' 이라는 말 처럼 다시 특정 부분으로 되돌아가서 탐색을 이어감으로써, 경우의 수를 탐색하는 기법을 의미합니다. 예를 들어 앞서 예로 들었던 벡터 v={1,2,3}를 활용하여 모든 경우의 수(3P3)를 탐색하는 과정을 도식화 하면 다음과 같습니다:

위의 그림은 간단한 전체 탐색 방법입니다. 요소가 많지 않지만, 여기에서 백트래킹 방식이 활용됩니다. 가령 처음 1->2->3 순서로 탐색하는 경우, 우선 1을 기점으로 다음 조합 가능한 방법을 탐색해야 합니다. 1을 기점으로 다음 조합은 2와 3으로 시작하는 방법이 있습니다. 두 번째 레벨에서 2로 시작하는 경우, 이제 다음 레벨에서 선택 가능한 요소는 3밖에 없습니다. 만약 요소가 4까지 있었다면 2를 기점으로 3과 4의 조합을 다시 비교해 나갈 것입니다. 현재 1->2->3 순서의 탐색 이후 1->3->2 순서를 탐색했고, 이후에는 2를 첫 기점으로 시작하여 앞선 방법과 같이 다시 비교해 나갈 것입니다. 이런식으로 하위 레벨의 가능한 모든 조합을 찾아 나가는 방법이 백트래킹입니다.

이러한 순열과 조합은 함수를 활용하여 재귀적으로 구현하거나 STL의 'Algorithm' 라이브러리를 활용한 next_permutaion 등의 알고리즘을 활용하여 구현할 수 있습니다.

Next_Permutation을 활용한 구현

Next_Permutation은 말 그대로 순열을 구현하기 위한 알고리즘입니다. C++ 벡터의 index 순서를 조절하여 그 기능을 수행합니다. 기본적인 사용법은 아래와 같습니다.

# default(1)	
template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
# custom(2)	
template <class BidirectionalIterator, class Compare>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

여기에서 BidirectionalIterator 파라미터에 우리가 흔히 알고 있는 Vector의 iterator를 활용하면 됩니다. default 함수는 위의 default 1에 해당하고, custom2의 경우, 순열을 돌리는 도중 어떠한 비교 행위가 필요한 경우 Compare 파라미터를 활용하면 됩니다.
(이와 같이 대부분의 STL의 Algorithm 라이브러리 함수들은 함수를 오버로딩하여 해당 기능이 동작하는 도중에 어떠한 비교행위를 할 수 있도록 구현해 두었습니다. 보통 이러한 Compare 파라미터의 경우, Bool 타입 함수를 콜백하여 현재 Iterator 간 값의 비교를 위해 사용됩니다. 이 부분은 추후에 별도로 다루도록 하겠습니다.)

next_permutation을 활용하면 앞서 언급한 벡터 v원소들의 모든 경우의 수 (3P3)을 아래와 같이 구현할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void permute()
{
    //벡터 값 그대로 사용하여 순열을 돌림
    vector<int> v = {1,2,3};

    do{
        for(int i = 0; i<v.size(); i++)
        {
            cout << v.at(i) << ' ';
        }

        cout << '\n';

    }while(next_permutation(v.begin(),v.end()));
}

int main()
{
    permute();
    
	return 0;
}

결과:

이 기능을 응용하면 물론 중복을 제외한 조합도 구현할 수 있습니다. 특히 알고리즘 문제에 따라 백트래킹 방식을 활용해야 하는 경우, 물론 위와 같이 모든 조합의 경우도 있지만, 중복된 집합은 제외하고 출력하고자 하는 경우도 있습니다.

예를 들어 6가지의 원소에서 4가지 요소들만 추출하여 조합하되, 중복은 피하고자 하는경우(6C4) 아래와 같이 구현할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void permute()
{
    // 벡터 값이 0인 인덱스를 가지고 조합을 진행한다.
    // nCr --> n=전체 값 6, r=조합 개수 4. 6C4
    vector<int> v = {0, 0, 0, 0, 1, 1};

    do{
        for(int i = 0; i<v.size(); i++)
        {
            if(v.at(i) == 0)
                cout << i+1 << ' ';
        }

        cout << '\n';

    }while(next_permutation(v.begin(),v.end()));
}

int main()
{
    permute();
    
	return 0;
}

결과:

참고로 위의 next_permutation 방식의 역순으로 조합을 탐색하고자 한다면 'prev_permutation' 라이브러리 함수를 사용하면 됩니다. 사용 방법은 next_permutation과 같습니다.

재귀를 활용한 방법

앞서 예시로 보인 6C4를 아래와 같이 재귀적으로 구현할 수도 있습니다. 아래 Permute 함수가 재귀적으로 구현되어 있고, 스택 라이브러리를 활용하여 값을 계속 push, pop 하는 것을 확인할 수 있습니다.

// nCm → 모든 경우의 수를 찾음. 중복 없음.
// 재귀를 활용함

#include <iostream>
#include <stack>
#include <vector>
 
using namespace std;
 
int n = 6;
int m = 4;
stack<int> st;

void print()
{
    vector<int> tmp_vec;
    stack<int> tmp_st = st;
    
    while(!tmp_st.empty())
    {
        tmp_vec.push_back(tmp_st.top());
        tmp_st.pop();
    }
    
    for(vector<int>::iterator itr = tmp_vec.end()-1; itr >= tmp_vec.begin(); itr--)
        cout << *itr << " ";
    
    cout << endl;
    return;
}

void permute(int count)
{
    if (st.size() == m)
        print();
 
    for (int i = count; i <= n; i++)
        
        if (st.size() < m)
        {
            st.push(i);
            
            permute(i + 1);
            
            st.pop();
        }
}

int main()
{
    permute(1);
    
    return 0;
}

스택을 사용한 이유는, 경우의 수를 찾아가는 과정에서 현재의 뎁스(depth)에서 값을 임시로 넣고 빼내기 위함입니다. 예를 들어, 우선 첫 뎁스(1)에서 1을 stack에 저장(st.push(i))합니다. 그리고 현재 stack이 조합 최대 개수인 r (여기서 4)보다 작으면, 즉 우리가 조합하기 위한 4개의 수를 아직 조합하지 않은 경우라면, 다음 뎁스의 값을 구하기 위해 permute(i+1)을 통해 다음 뎁스로 넘어갑니다. 즉, permute 함수 자체가 현재의 뎁스를 의미함을 알 수 있습니다.

이제 뎁스(2)가 되었습니다.

뎁스2에서 이제 가능한 수는 2,3,4,5,6 입니다. 가장 먼저 올 수 있는 수는 2 이므로, stack에 저장하고 다시 permute() 함수를 호출하여 다음 뎁스(3)으로 넘깁니다. 이런식으로 뎁스(3),(4)까지 넘기면 첫 조합인 {1,2,3,4}가 완성됩니다.

처음 조합을 완성되면 이후에는 어떻게 될까요? 마지막 재귀 중인 permute(i+3) 함수 내부에서 우선 print함수를 호출하여 전체 스택에 저장된 값을 출력합니다. 현재 {1,2,3,4}가 저장되어 있는 상태죠. 그 이후에는 현재 permute(i+3)이 종료되면서 stack에서 마지막 숫자인 4를 pop (st.pop())합니다. 그러면 다시 {1,2,3}이 되죠. 그 이후에 현재 count(4)의 상태에서 count +1 = 5 가 되고 스택에 다시 넣습니다. 다시 스택에 저장된 전체 수가 4가 되었으므로 다음 permute에서 {1,2,3,5}를 출력합니다. 이런식으로 뎁스를 이동하며 stack pop과 push를 반복하여 전체 경우의 수를 탐색해 나갑니다.

저작자표시 비영리 변경금지

'Development > Algorithm' 카테고리의 다른 글

[알고리즘 / C++] DFS(깊이 우선 탐색) 알고리즘 개념 및 스택과 재귀를 활용한 구현 (0)	2020.01.01
[Algorithm / C++] 인접행렬과 BFS (너비 우선 탐색) 알고리즘 및 구현 (0)	2019.12.26
[Algorithm / C++] String을 파싱하는 3가지 방법 (0)	2019.12.26

TAGS.

사막의 여우

사막의 여우

사막의 여우

연구

공유

소통

Blog Introduction

사막의 여우

사막의 여우