06. (모두의 알고리즘)하노이의 탑 옮기기
- 하노이의 탑 규칙
- 크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮김
- 원반은 한 번에 한 개씩만 옮길 수 있음
- 원반을 옮길 때는 한 기둥의 맨 위 원반을 뽑아 다른 기둥의 맨 위로만 옮길 수 있음
- 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없음
- 하노이의 탑 풀이
- 원반이 1개일 때
- 1번 기둥의 원반을 3번 기둥으로 옮김
- 원반이 2개일 때
- 1번 기둥의 맨 위 원반을 2번 기둥으로 옮김
- 1번 기둥의 큰 원반을 3번 기둥으로 옮김
- 2번 기둥의 원반을 3번 기둥으로 옮김
- 원반이 3개일 때
- 1번 기둥의 위 원반 2개를 2번 기둥으로 옮김
- 1번 기둥의 남은 원반을 3번 기둥으로 옮김
- 2번 기둥의 원반 2개를 3번 기둥으로 옮김
- 원반이 n개일 때
- 1번 기둥의 n-1개 원반을 2번 기둥으로 옮김
- 1번 기둥의 남은 원반을 3번 기둥으로 옮김
- 2번 기둥의 원반 n-1개를 3번 기둥으로 옮김
- 원반이 1개일 때
- 하노이의 탑 옮기기
123456789101112131415161718def hanoi(n, from_pos, to_pos, aux_pos):if n == 1:print(from_pos, "->", to_pos)returnhanoi(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) - 계산복잡도
- O(1)
- O(n)
- O(n^2)
- O(2^n)
- 재귀 호출의 원리를 이용한 컴퓨터 그래픽 .
- spiral
- triangle
- tree
- snow