하노이의 탑 이동 문제 - soo:bak
작성일 :
하노이의 탑이란?
하노이의 탑(Tower of Hanoi) 문제는 세 개의 기둥과 여러 개의 원판이 주어졌을 때, 특정 규칙을 따라 모든 원판을 다른 기둥으로 옮기는 고전적인 재귀 퍼즐입니다.
문제의 조건은 다음과 같습니다:
- 한 번에 하나의 원판만 이동할 수 있다.
- 항상 맨 위에 있는 원판만 옮길 수 있다.
- 더 큰 원판은 더 작은 원판 위에 놓을 수 없다.
이러한 조건 아래에서 가장 작은 횟수로 모든 원판을 옮기는 방법을 구하는 것이 목표입니다.
문제의 재귀적 구조 분석
하노이의 탑 문제는 재귀 호출 구조를 직관적으로 이해할 수 있는 대표적 예시입니다.
N개의 원판이 시작 기둥에 쌓여 있고, 이를 도착 기둥으로 옮기려면 다음과 같은 전략을 취해야 합니다:
- 위의
N - 1개의 원판을 보조 기둥으로 재귀적으로 옮긴다. - 가장 아래에 있는 가장 큰 원판을 목적지 기둥으로 이동한다.
- 보조 기둥에 있는
N - 1개의 원판을 다시 목적지 기둥으로 재귀적으로 옮긴다.
이 과정은 각 단계에서 같은 방식으로 다시 하노이 문제를 호출하므로,
문제 자체가 더 작은 하노이 문제로 분할되는 구조를 가집니다.
예시: N = 3일 때의 호출 흐름
1
2
3
4
5
6
7
8
9
10
H(3, 1, 2, 3)
├── H(2, 1, 3, 2)
│ ├── H(1, 1, 2, 3) → move 1 → 3
│ └── move 2 → 2
│ └── H(1, 3, 1, 2) → move 3 → 2
├── move 3 → 3
└── H(2, 2, 1, 3)
├── H(1, 2, 3, 1) → move 2 → 1
└── move 1 → 3
└── H(1, 1, 2, 3) → move 1 → 3
위 호출 트리를 보면, 재귀가 깊어지며 전체 문제를 절반씩 나누어 다루고 있음을 알 수 있습니다.
이처럼 하노이의 탑은 각 문제를 더 작은 동일한 문제로 분할해 해결하는 방식이기 때문에,
‘divide and conquer’ (분할 정복) 전략의 구조를 가지며,
각 단계에서 정확히 무엇을 해야 하는지가 명확히 정의되어 있습니다.
이동 횟수 점화식 및 일반식 유도
하노이의 탑 문제는 단순히 원판을 옮기는 구현을 넘어서,
반복적 구조와 점화식을 통해 수학적으로도 구조를 해석할 수 있는 대표적인 알고리듬 문제입니다.
전체 이동 횟수는 다음과 같은 점화식을 따릅니다:
점화식 정의
\[T(1) = 1\] \[T(n) = 2T(n-1) + 1\]
이 점화식은 이전 단계에서 n - 1개의 원판을 옮기고, 1개의 큰 원판을 이동하고,
다시 n - 1개의 원판을 옮기는 과정을 의미합니다.
점화식 전개
점화식을 여러 번 전개해 보면 다음과 같습니다:
\[\begin{aligned} T(n) &= 2T(n-1) + 1 \\ &= 2(2T(n-2) + 1) + 1 \\ &= 4T(n-2) + 2 + 1 \\ &= 4(2T(n-3) + 1) + 2 + 1 \\ &= 8T(n-3) + 4 + 2 + 1 \\ &\;\vdots \\ &= 2^{k}T(n-k) + (2^{k} - 1) \end{aligned}\]
\(k = n - 1\)일 때,
\(T(1) = 1\)이므로 다음과 같이 정리됩니다:
\[\begin{aligned} T(n) &= 2^{n - 1} \cdot T(1) + (2^{n - 1} - 1) \\ &= 2^{n - 1} + (2^{n - 1} - 1) = 2^n - 1 \end{aligned}\]일반식 도출
결과적으로 다음과 같은 이동 횟수 일반식이 도출됩니다:
\[T(n) = 2^n - 1\]이 식은 하노이 문제의 크기 n에 따라 지수적으로 증가하는 실행 횟수를 보다 명확히 보여줍니다.
시간 복잡도
하노이의 탑 문제는 위에서 도출한 수식에 따라 다음과 같은 시간 복잡도를 가집니다:
시간 복잡도: \(O(2^n)\)
즉, 입력값이 증가할수록 실행 시간이 기하급수적으로 증가하는 구조적 특성을 보여줍니다.
따라서, 입력 크기가 조금만 커져도 연산량이 수백만, 수억 단위로 증가하게 되므로,
일정 수준을 넘어서면 현실적으로 실행이 불가능해지는 한계에 직면하게 됩니다.
예제 코드 (C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
void hanoi(int n, int from, int via, int to) {
if (n == 1) {
cout << from << " " << to << "\n";
return;
}
hanoi(n - 1, from, to, via);
cout << from << " " << to << "\n";
hanoi(n - 1, via, from, to);
}
int main() {
int n;
cin >> n;
cout << (1 << n) - 1 << "\n"; // 이동 횟수
hanoi(n, 1, 2, 3);
return 0;
}
마무리
하노이의 탑 문제는 단순한 조건과 규칙 속에 분할 정복 구조와 수학적 성질이 결합된 대표적인 재귀 문제입니다.
- 핵심은 반복되는 구조의 규칙 파악과 이를 통한 재귀적 사고
- 최소 이동 횟수는
2^n - 1