Hanoi Tower   하노이 탑

(2019-02-02)

하노이의 탑

1. 하노이 탑 (Hanoi Tower)재귀(Recursion) 문제의 일종
     - 재귀 호출을 이용해서 풀 수 있는 가장 유명한 예제

  ※ 문제 고안 : 1883년 프랑스 수학자 루카스(Edouard Lucas, 1842~1891)


2. 문제 기술(記述)

  ㅇ 문제 조건
     - 3개 막대가 고정되어 있고, 중심에 구멍이 뚫려진 반경이 다른 n개 원반이 있음

  ㅇ 문제 목표
     - 원반을 하나씩 이동시켜 탑 전체를 다른 기둥으로 옮기는 것

  ㅇ 문제 규칙
     - ① 1회에 1개 원반 만 이동
     - ② 작은 원반 위에 큰 원반을 올려놓을 수 없음

  ㅇ (최선의) 이동 횟수 계산
     - (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


[알고리즘] 1. 알고리즘 2. 알고리즘 설계 3. 계산 복잡도 4. 하노이 탑 5. 순서도 6. 재귀 호출
[알고리즘 종류]

 
        최근수정     요약목록     참고문헌