Hanoi Tower   하노이 탑

(2020-10-08)

하노이의 탑


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



Copyrightⓒ written by 차재복 (Cha Jae Bok)
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"