문제 풀이를 위한 프로그래밍 기법 - 2. 재귀적 알고리즘

이번 포스트에서는 문제 풀이를 위한 프로그래밍 기법 두번째 재귀적 알고리즘에 대해서 알아보도록 하겠습니다.

재귀를 사용하면 알고리즘을 잘 구현할 수 있게 되는 경우가 많이 있습니다.(안좋은 경우도 있지만)

문제 풀이를 하면서 답이 될 수 있을 만한 재귀적 풀이 후보들을 소개해보고자 합니다.

 

1. 부분집합 생성하기

재귀를 사용하는 예 중 부분집합 생성하기에 대해 살펴보도록 하겠습니다.

원소가 n개인 집합의 모든 부분집합을 생성하는 알고리즘을 구현해야하는 상황에 있다고 생각해봅시다.

{1, 2, 3}의 부분집합은 (공집합), {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} 이렇게 있습니다.

우선 부분집합을 구하는 search라는 함수는 다음과 같은 벡터를 사용합니다.

vector<int> subset;

위 벡터에는 각 부분집합의 원소가 저장됩니다. 함수의 parameter를 1을 주고 호출합니다.

// n은 집합의 원소의 개수를 말합니다
void search(int input) {
    if (input == n + 1) {
        // 부분집합을 처리한다.
    } else {
        // input을 부분집합에 포함시킨다.
        subset.push_back(input);
        search(input + 1);
        
        subset.pop_back();
        // input을 부분집합에 포함시키지 않는다
        search(input + 1);
    }
}

 

 

                             search(1)

             search(2)                       search(2)

   search(3)      search(3)      search(3)       search(3)

    |       |                 |       |                   |     |                   |       |

{공집합}, {3}     {2}, {2,3}        {1}, {1,3}      {1,2} {1,2,3}

 

작동 방식은 위 그림과 같습니다.(열심히 그린게 아니라 입력했는데...)

최종적으로 나오는 것은 부분집합이 됩니다.

 

2. 순열 생성하기

원소가 n개의 집합의 모든 순열을 생성하는 알고리즘을 구현해보도록 합시다.

예를 들어 (1, 2, 3)의 순열은 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) 이렇습니다.

이번에도 재귀를 사용합니다.

vector<int> permutation;

bool chosen[n + 1];

위 배열은 각 원소를 순열에 포함했는지 여부를 나타내는 것입니다. (n은 원소의 개수를 나타냅니다.)

이제 순열을 생성하는 재귀 함수를 살펴보겠습니다.

void search() {
    if (permutation.size() == n ) {
        // 순열을 처리한다.
    } else {
        for (int i = 1; i <= n; i++) {
            if( chosen[i] ) continue;
            chosen[i] = true;
            permutation.push_back(i);
            search();
            chosen[i] = false;
            permutation.pop_back();
        }
    }
}

함수를 호출할 때마다 새로운 원소를 순열에 추가하고, 그 원소를 선택했다는 것을 chosen 배열에 기록합니다.

그러다가 permutation의 크기가 원소의 개수와 같아지게 되면 하나의 순열이 생기게 되는 것입니다.

순열이 생기면 순열을 순열을 저장하는 곳에 옮기고 permutation vector를 다시 지우고 또 순열을 생성하면서 순열을 구하면 될 것 같습니다.

 

3. 퇴각 검색(Backtracking)

백트래킹(Backtracking)은 비어있는 해로 탐색을 시작하고 단계마다 해를 확장해 나가는 방식의 알고리즘을 말하는데 탐색 과정에서 해를 생성하는 모든 방법을 재귀적으로 살펴보게 됩니다.

크기가 n * n 인 체스판에 n개의 퀸을 서로 공격할 수 없도록 배치하는 방법의 수를 세는 예제를 살펴보도록 합시다.

	O
			O
O
		O

	O
			O
O
		O

 

 

4 * 4 체스판에 대해서 해 2가지를 표현한 것입니다.

1행부터 n행까지 반복하면서 정확히 하나의 퀸을 배치하는데, 그 퀸이 이전 단계에서 배치한 퀸을 공격할 수 없는 위치에 배치합니다.

체스판에 n개의 퀸을 모두 배치하면 하나의 해를 구한 것입니다.

이 알고리즘을 구현하면 아래 코드와 같이 됩니다.

void search(int y) {
    if(y == n) {
        count++;
        return;
    }
    for(int x = 0; x < n; x++) {
        if(col[x] || diag1[x + y] || diag2[x - y + n - 1] = 1;
        col[x] = diag1[x + y] = diag2[x - y + n - 1] = 1;
        search(y + 1);
        col[x] = diag1[x + y] = diag2[x - y + n - 1] = 0;
    }
}

알고리즘의 수행과정을 살펴보도록 하겠습니다.

search(0)을 호출하면 탐색이 시작됩니다. 체스판의 크기는 n입니다.(n x n) 해의 개수는 count에 저장하며, 행과 열의 번호가 0부터 n - 1까지라고 칩시다.

search 함수의 인자가 y일 때 이 함수는 퀸을 y번 행에 배치하고 인자를 y + 1로 주고 함수를 재귀적으로 호출합니다.

그러다가 y가 n과 같아지면 하나의 해를 구했으므로 count의 값을 하나 증가시켜줍니다.

배열 col은 퀸이 포함된 열을 추적하기 위한 것이고 배열diag1과 diag2는 대각선을 추적하기 위한 것입니다.

 

 

퀸이 이미 배치된 열, 혹은 대각선에 퀸을 추가로 배치할 수는 없습니다. 

n이 증가할 수록 가능한 방법의 수는 지수적으로 증가하기 때문에 탐색의 시간은 급격하게 느려집니다.

가령 16 x 16 체스판에 퀸을 배치하는 방법의 수는 14,772,512가지인데 이를 구하면 분 단위가 걸립니다.

 

 

 

 

 

 

 

이렇게 재귀함수를 사용한 알고리즘에 대해 살펴보았습니다.

다음 포스트에서는 비트 연산에 대해 살펴보도록 하겠습니다.