Hanoi Tower   하노이 탑

(2019-08-25)

하노이의 탑

Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공업일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
기초과학 >   1. 과학
[수학]
[물리]
[화학]
[지구,천체 과학]
[생명과학]
[뇌과학]
수학 >   1. 수학
[기초수학]
[집합,논리]
[해석학(미적분 등)]
[대수학]
[확률/통계]
[수치해법]
기초수학 > [수학(기초일반)]
[비교 (같음/닮음/다름)]
[지수,로그]
[복소수]
[수열,급수]
[좌표계]
[기하학]
수열,급수 > [수열]
[급수]
수열   1. 수열
  2. 수열 용어
  3. 수열 종류
  4. 점화식
  5. 피보나치 수열
  6. 하노이의 탑

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

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.   기초과학
        1. 과학
    1.   수학
          1. 수학
      1.   기초수학
        1.   수학(기초일반)
        2.   비교 (같음/닮음/다름)
        3.   지수,로그
        4.   복소수
        5.   수열,급수
          1.   수열
            1.   1. 수열
                2. 수열 용어
                3. 수열 종류
                4. 점화식
                5. 피보나치 수열
                6. 하노이의 탑
          2.   급수
        6.   좌표계
        7.   기하학
      2.   집합,논리
      3.   해석학(미적분 등)
      4.   대수학
      5.   확률/통계
      6.   수치해법
    2.   물리
    3.   화학
    4.   지구,천체 과학
    5.   생명과학
    6.   뇌과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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