Algorithm

tower of hanoi

algorithm, python, tower of hanoi

  • Tower of Hanoi(하노이 탑)

    • 반드시 큰 쟁반이 아래에 있어야 한다.
    • 큰 쟁반이 작은 쟁반보다 위에 있을 수 없다.
    • 기둥1(_from), 기둥2(_by), 기둥3(_to)이 있다.

    • 기둥 1에서 기둥3으로 모두 이동시켜야 한다.

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      # (num - 1)개를 _from에서 _to를 이용하여 _by로 이동시킨다.
      # num(제일 큰 쟁반)을 _from에서 _to로 이동시킨다.
      # (n - 1)개를 _by에서 _from을 이용하여 _to로 이동시킨다.

      def hanoi(num, _from, _by, _to):
          #base case
          if num == 1:
              print(f'{_from}에서 {_to}로 {num}번째 쟁반 이동')
              return

          
          hanoi(num - 1, _from, _to, _by)
          print(f'{_from}에서 {_to}로 {num}번째 쟁반 이동')
          hanoi(num - 1, _by, _from, _to)

    • 함수가 동작하는 모습을 stack frame으로 그려본다.

    • “pythontutor.com”을 이용하여 함수가 동작하는 모습을 보는 것도 좋다.
    • 점화식 및 기저 조건을 잘 만드는 것이 중요하다.
    • stack frame에 쌓이는 모습을 call stack이라고 한다.
    • call stack 맨 위에 있는 frame이 실행 권한을 가진다.

    • 함수가 실행이 끝나지 않은 상태에서 위 frame에 실행 권한을 주는 것을 blocking이라고 한다.

      1
      2
      3
      4
      5
      6
      7
      8
      hanoi(3, 'A', 'B', 'C')
      >> A에서 C로 1번째 쟁반 이동
         A에서 B로 2번째 쟁반 이동
         C에서 B로 1번째 쟁반 이동
         A에서 C로 3번째 쟁반 이동
         B에서 A로 1번째 쟁반 이동
         B에서 C로 2번째 쟁반 이동
         A에서 C로 1번째 쟁반 이동
Share