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. 재귀 호출
[알고리즘 종류]
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램,프로그래밍
      1.   프로그래밍 언어론
      2.   구조적 프로그래밍
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 알고리즘 설계
            3. 계산 복잡도
            4. 하노이 탑
            5. 순서도
            6. 재귀 호출
        1.   알고리즘 종류
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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