1. 하노이 탑 (Hanoi Tower)
ㅇ 재귀(Recursion) 문제의 일종
- 재귀 호출을 이용해서 풀 수 있는 가장 유명한 예제
※ 문제 고안 : 1883년 프랑스 수학자 루카스(Edouard Lucas, 1842~1891)
2. 하노이 탑 문제의 기술(記述)
ㅇ 문제 조건
- 3개 막대가 고정되어 있고, 중심에 구멍이 뚫려진 반경이 다른 n개 원반이 있음
ㅇ 문제 목표
- 원반을 하나씩 이동시켜 탑 전체를 다른 기둥으로 옮기는 것
ㅇ 문제 규칙
- ① 1회에 1개 원반 만 이동
- ② 작은 원반 위에 큰 원반을 올려놓을 수 없음
3. 하노이 탑 문제에서, (최선의) 이동 횟수를 계산하는 방식
ㅇ (n장의 원반을 이동하는 패턴)
- 먼저, (n-1)장을 이동한 후에,
- 그 다음, 제일 밑의 가장 큰 원반 1장을 이동하고,
- 다시, (n-1)장을 이동하는 것으로 생각할 수 있음
ㅇ (이로부터, 재귀적인 구조가 있음을 알 수 있음)
- 즉, 큰 규모가 작은 규모의 문제로 풀 수 있음
- n장을 이동하는 횟수를 T(n)이라 하면,
- 점화식은, T(n) = 2 x T(n-1) + 1 가 됨
ㅇ (이로부터, 전체를 설명하는 일반항 표현이 가능)
- T1 = 1
- Tn = 2Tn-1 + 1
- 일반항 : Tn = 2n -1