06. (모두의 알고리즘)하노이의 탑 옮기기

Posted on: 2018-09-27 2018-10-09
Categories: 강의자료, 파이썬

하노이의 탑 규칙
1. 크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮김
2. 원반은 한 번에 한 개씩만 옮길 수 있음
3. 원반을 옮길 때는 한 기둥의 맨 위 원반을 뽑아 다른 기둥의 맨 위로만 옮길 수 있음
4. 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없음
하노이의 탑 풀이
1. 원반이 1개일 때
  1. 1번 기둥의 원반을 3번 기둥으로 옮김
2. 원반이 2개일 때
  1. 1번 기둥의 맨 위 원반을 2번 기둥으로 옮김
  2. 1번 기둥의 큰 원반을 3번 기둥으로 옮김
  3. 2번 기둥의 원반을 3번 기둥으로 옮김
3. 원반이 3개일 때
  1. 1번 기둥의 위 원반 2개를 2번 기둥으로 옮김
  2. 1번 기둥의 남은 원반을 3번 기둥으로 옮김
  3. 2번 기둥의 원반 2개를 3번 기둥으로 옮김
4. 원반이 n개일 때
  1. 1번 기둥의 n-1개 원반을 2번 기둥으로 옮김
  2. 1번 기둥의 남은 원반을 3번 기둥으로 옮김
  3. 2번 기둥의 원반 n-1개를 3번 기둥으로 옮김

하노이의 탑 옮기기

def hanoi(n, from_pos, to_pos, aux_pos):
    if n == 1:
        print(from_pos, "->", to_pos)
        return

    hanoi(n - 1, from_pos, aux_pos, to_pos)
    print(from_pos, "->", to_pos)
    hanoi(n - 1, aux_pos, to_pos, from_pos)


print("\nn = 2")
hanoi(2, 1, 3, 2)

print("\nn = 3")
hanoi(3, 1, 3, 2)

print("\nn = 5")
hanoi(5, 1, 3, 2)

def hanoi(n, from_pos, to_pos, aux_pos):

if n == 1:

print(from_pos, "->", to_pos)

return

hanoi(n - 1, from_pos, aux_pos, to_pos)

print(from_pos, "->", to_pos)

hanoi(n - 1, aux_pos, to_pos, from_pos)

print("\nn = 2")

hanoi(2, 1, 3, 2)

print("\nn = 3")

hanoi(3, 1, 3, 2)

print("\nn = 5")

hanoi(5, 1, 3, 2)

계산복잡도
1. O(1)
2. O(n)
3. O(n^2)
4. O(2^n)
재귀 호출의 원리를 이용한 컴퓨터 그래픽 .
1. spiral
2. triangle
3. tree
4. snow

whan0623

277