하노이탑 규칙
- 한 번에 하나: 원판은 한 번에 하나만 옮깁니다.
- 맨 위만: 각 기둥의 가장 위에 있는 원판만 옮길 수 있습니다.
- 큰 것은 아래로: 작은 원판 위에 큰 원판을 올릴 수 없습니다.
- 목표: 왼쪽 기둥의 원판을 모두 오른쪽 기둥으로 같은 순서대로 옮기면 끝입니다.
최소 이동 횟수 공식
원판 n개를 옮기는 데 필요한 최소 횟수는 2ⁿ − 1입니다.
| 원판 수 | 최소 이동 횟수 |
|---|---|
| 3개 | 7번 |
| 4개 | 15번 |
| 5개 | 31번 |
| 6개 | 63번 |
| 7개 | 127번 |
| 8개 | 255번 |
원판이 하나 늘면, 위의 원판들을 옆으로 비켜 두었다가(앞의 횟수) 가장 큰 원판을 옮기고(1번) 다시 위에 올려야(앞의 횟수) 하므로 횟수가 두 배보다 하나 더 늘어납니다.
하노이탑 푸는 법
- 가장 작은 원판의 길: 원판 수가 짝수면 가장 작은 원판을 왼쪽 → 가운데 → 오른쪽 → 왼쪽 … 순서로, 홀수면 왼쪽 → 오른쪽 → 가운데 → 왼쪽 … 순서로 돌립니다.
- 번갈아 두기: 가장 작은 원판을 한 번 옮긴 뒤에는, 작은 원판이 아닌 원판 중 옮길 수 있는 단 하나를 옮깁니다. 이 두 가지를 번갈아 하면 최소 횟수로 풀립니다.
- 거꾸로 생각하기: "가장 큰 원판을 오른쪽에 놓으려면 나머지를 모두 가운데로 비켜야 한다"처럼 큰 원판부터 생각하면 길이 보입니다.
하노이탑 자주 묻는 질문
하노이탑은 어떻게 하나요?
왼쪽 기둥에 크기 순서로 쌓인 원판을 모두 오른쪽 기둥으로 옮기면 됩니다. 한 번에 원판 하나만, 각 기둥의 맨 위 원판만 옮길 수 있고, 작은 원판 위에 큰 원판을 올릴 수 없습니다. 기둥을 눌러 원판을 들고, 옮길 기둥을 누르면 내려놓습니다.
최소 이동 횟수는 몇 번인가요?
원판이 n개면 최소 2ⁿ−1번입니다. 3개는 7번, 4개는 15번, 5개는 31번, 8개는 255번입니다. 원판이 하나 늘 때마다 최소 횟수가 두 배보다 한 번 더 늘어납니다.
풀이 보기는 어떻게 움직이나요?
가장 짧은 풀이를 차례로 보여 줍니다. 위의 n−1개를 가운데 기둥으로 옮기고, 가장 큰 원판을 오른쪽으로 옮긴 뒤, n−1개를 다시 그 위로 옮기는 방법(재귀)입니다.
키보드로도 할 수 있나요?
숫자 1·2·3 키가 왼쪽·가운데·오른쪽 기둥입니다. 원판을 들 기둥 번호를 누르고, 내려놓을 기둥 번호를 누르면 됩니다.
수업에 써도 되나요?
네. 재귀와 2의 거듭제곱을 설명할 때 많이 쓰는 퍼즐입니다. 원판 3~4개로 직접 해 보게 한 뒤 풀이 보기로 규칙을 찾아보면 좋습니다.