[C][순환] 하노이의 탑 계산

하노이의 탑(The Tower of Hanoi)은 수학적인 퍼즐이자 게임이다. 하노이의 탑은 세 개의 기둥과, 이 기둥에 꽂을 수 있는 서로 다른 크기의 원판들로 구성된다. 원판들은 한 기둥에 정렬 되어 있는데, 아래에서 위로 갈 수록 원판의 크기가 작아진다. 퍼즐의 목표는 전체 원판들을 다른 하나의 기둥으로 옮기는 것인데, 이 때 다음과 같은 간단한 규칙을 따라야 한다.

• 한 번에 하나의 원판만을 옮길 수 있다.
• 원판을 옮길 때는 맨 위의 원판을 다른 기둥으로 옮겨야 한다.
• 큰 원판을 작은 원판 위에 올릴 수 없다.

원판의 개수가 커질 수록 문제가 복잡해지기 때문에 순환적으로 접근해보자.

순환 알고리즘에서는 순환이 이루어질 때 마다 문제의 크기가 작아진다.

하노이의 탑에서는 옮겨야 하는 원판의 수가 문제의 크기이자 줄여야 하는 대상이다.

그러기 위해 먼저 대략적인 알고리즘을 살펴보겠다.

기둥 A, B, C가 존재하고 기둥 A에 있는 원판을 기둥 C로 옮기는 것을 목표로 한다.

먼저 원판이 한 개인 경우, 이 때는 그저 원판을 A에서 C로 옮기면 그만이다.

원판이 두 개 이상(n개)이면 일단 맨 밑에 있는 원판을 제외한 모든 원판들을 B로 옮긴다.

그 후 맨 밑의 원판을 C로 옮기고, B에 있는 남아있는 원판들을 다시 C로 옮기면 된다.

이 때 B에 남아 있는 원판들을 다시 C로 옮기는 것은 결국 n-1개의 원판을 기둥 B에서 A를 사용해 C로 옮기는 것과 같다.

즉 다시 한 번 이 알고리즘을 실행하되 문제의 크기인, 옮겨야할 원판의 개수는 n개에서 n-1개로 감소하였다.

순환을 하게 되면서 문제의 크기가 줄어든 것이다.

다음으로는 위의 알고리즘을 이용해 실제 코드를 작성해보았다.

#include <stdio.h>
 
void hanoi(int n, char from, char temp, char to) {
    if(n == 1) printf("원판 1 // %c ==> %c\n", from, to);
    else {
        hanoi(n-1, from, to, temp);
        printf("원판 %d // %c ==> %c\n", n, from, to);
        hanoi(n-1, temp, from, to);
    }
}
 
int main(void) {
    int n = 3;
    char from = 'A', temp = 'B', to = 'C';
    
    hanoi(n, from, temp, to);
    
    return 0;
}

하노이의 탑을 계산하는 프로그램의 시간 복잡도를 구하는 과정은 다음과 같다.

먼저 하노이의 탑에서 n개의 원판을 옮기는데 필요한 연산의 수를 구해보자.

이 때 A(n)을 필요한 연산의 수라고 할 것이다.

위의 알고리즘에서 우리는 n개의 원판을 옮길 때 n-1개의 원판을 먼저 옮기고, 그 후 가장 아래의 1개의 원판을 옮긴 다음, 다시 n-1개의 원판을 옮겼다.

이를 식으로 바꿔주면 A(n) = A(n-1) + 1 + A(n-1) = 2A(n-1) + 1 이다.

이 때 A(n-1) = 2A(n-2) + 1 이므로 이를 대입하면 A(n) = 2 ^ 2 * A(n-2) + 2 + 1 이고,

또 A(n-2)는 2A(n-3) + 1임을 이용해 우리는 A(n) = 2^3 * A(n-3) + 4 + 2 + 1 인 것을 알 수 있다.

이 과정을 반복하다보면 결국 A(n) = 2^n-1 * A(1) + ....  + 2^2 + 2^1 + 2^0 이 된다. 

A(1)은 1이니, A(n)은 n개의 항을 가지고, 초항이 1, 공비가 2인 등비수열의 합이다.

따라서 총 연산의 개수는 A(n) = 1*(2^n - 1) / 2 - 1 = 2^n - 1이고, 시간복잡도는 O(2^n)가 된다.

A(n) = 2A(n-1) + 1에서 점화식을 이용할 수 도 있다.

A(n+1) = 2A(n) + 1 일 때 A(n+1) + 1 = 2(A(n)+1)이다.

B(n) = A(n) + 1이라 가정하였을 때, B(n+1) = 2B(n)이다.

이 때 B(n)은 첫째 항이 B(1) = A(1) + 1 = 2 이고 공비가 2인 등비수열이다.

따라서 B(n) = 2 * 2^(n-1) = 2^n 이고 B(n) = A(n) + 1이므로, 총 연산의 개수 A(n)은 2^n - 1이고, 시간복잡도는 O(2^n)가 된다.

• 거듭제곱의 값 계산을 통해 순환 알고리즘과 반복 알고리즘 비교해보기
• 파보나치 수열의 계산을 통해 순환 알고리즘과 반복 알고리즘 비교해보기
• 이항 계수의 계산을 통해 순환 알고리즘과 반복 알고리즘 비교해보기