하노이탑
하노이탑은 세 기둥 가운데 왼쪽 기둥에 쌓인 원판을 오른쪽 기둥으로 모두 옮기는 퍼즐입니다. 한 번에 한 개씩, 맨 위 원판만 옮길 수 있고, 큰 원판을 작은 원판 위에 올릴 수는 없습니다. 이 페이지는 원판 3개로 바로 시작하고, 깨면 4개·5개로 하나씩 늘어 8개까지 이어집니다. 기둥을 눌러 원판을 들고 옮길 기둥을 누르거나, 원판을 끌어다 놓으면 됩니다. 이동 수와 최소 수, 걸린 시간이 늘 보이고, 최소 수로 깨면 별이 붙습니다. 막히면 '풀이 보기'를 눌러 정답 순서를 천천히 볼 수 있습니다.
규칙은 세 가지입니다
한 번에 원판 하나만 옮깁니다. 기둥 맨 위에 있는 원판만 들 수 있습니다. 큰 원판은 작은 원판 위에 올릴 수 없습니다. 이 세 가지만 지키며 왼쪽 기둥의 원판을 모두 오른쪽 '도착' 기둥으로 옮기면 깹니다. 규칙에 어긋난 수는 원판이 흔들리기만 하고 이동 수에 들어가지 않습니다.
최소 이동 수 공식: 2의 n제곱 빼기 1
원판이 n개일 때 가장 적게 옮기는 수는 2를 n번 곱한 값에서 1을 뺀 수입니다. 3개는 7번, 4개는 15번, 5개는 31번, 6개는 63번, 7개는 127번, 8개는 255번입니다. 원판이 하나 늘 때마다 최소 수가 두 배보다 하나 많아집니다. 위 줄의 '최소' 숫자가 이 값이고, 이 수 그대로 깨면 별이 붙습니다.
재귀 원리: 큰 문제를 작은 문제로
원판 n개를 오른쪽으로 옮기려면 먼저 위의 n-1개를 가운데 기둥으로 옮깁니다. 그다음 가장 큰 원판을 오른쪽으로 옮기고, 가운데의 n-1개를 다시 그 위로 옮깁니다. n-1개를 옮기는 일도 같은 방법으로 n-2개를 옮기는 일로 나뉩니다. 그래서 n개의 최소 수는 n-1개 최소 수의 두 배에 1을 더한 값이 되고, 이것을 풀면 2의 n제곱 빼기 1이 나옵니다. 컴퓨터 수업에서 재귀를 배울 때 가장 먼저 나오는 예제입니다.
손으로 풀 때 쉬운 요령
가장 작은 원판은 늘 같은 방향으로 한 칸씩 돌립니다. 원판 수가 홀수면 왼쪽에서 오른쪽 도착 기둥 쪽으로, 짝수면 가운데 기둥 쪽으로 먼저 옮깁니다. 작은 원판을 옮긴 다음 수는 작은 원판을 건드리지 않고 할 수 있는 수가 딱 하나뿐이라 그 수를 두면 됩니다. 이 두 가지를 번갈아 하면 최소 수로 끝납니다.
단계와 기록
원판 3개(1단)로 시작해 깨면 다음 단계로 저절로 넘어가 8개(6단)까지 이어집니다. 단계마다 가장 적은 이동 수와 가장 빠른 시간이 이 브라우저에 저장되고, 아래 '다시 하기'의 작은 글자로 지난 단계를 다시 할 수 있습니다. 하던 판은 새로고침해도 그대로 이어집니다.
사용법
- 기둥 누르기 원판이 있는 기둥을 누르면 맨 위 원판이 들립니다.
- 옮길 기둥 누르기 옮길 기둥을 누르면 원판이 놓입니다. 원판을 끌어다 놓아도 됩니다.
- 모두 오른쪽으로 모든 원판을 오른쪽 도착 기둥으로 옮기면 깨고 다음 단계로 넘어갑니다.
주요 기능
- 원판 3개부터 8개까지 저절로 이어지는 단계
- 누르기·끌기 둘 다 되는 조작
- 이동 수·최소 수·시간 표시, 최소 수로 깨면 별
- 정답 순서를 천천히 보여 주는 풀이 보기
- 단계별 최소 이동·최단 시간 기록, 새로고침해도 이어 하기
용어 설명
- 최소 이동 수
- 원판 n개를 옮기는 가장 적은 수, 2의 n제곱 빼기 1입니다.
- 재귀
- 큰 문제를 같은 모양의 작은 문제로 나누어 푸는 방법입니다.
빠른 참고
| 원판 3개 최소 수 | 7번 |
|---|---|
| 원판 8개 최소 수 | 255번 |
| 공식 | 2ⁿ - 1 |
자주 묻는 질문
하노이탑 최소 이동 횟수 공식은 무엇인가요?
원판이 n개일 때 2의 n제곱에서 1을 뺀 수입니다. 3개는 7번, 4개는 15번, 5개는 31번, 8개는 255번입니다.
왜 2의 n제곱 빼기 1이 되나요?
n개를 옮기려면 위의 n-1개를 가운데로, 가장 큰 원판을 오른쪽으로, n-1개를 다시 그 위로 옮겨야 합니다. 그래서 n개의 수는 n-1개 수의 두 배에 1을 더한 값이고, 이를 3개부터 차례로 계산하면 2의 n제곱 빼기 1이 됩니다.
별은 언제 붙나요?
위 줄의 '최소' 숫자와 똑같은 이동 수로 깨면 별이 붙습니다. 별을 받은 단계는 아래 '다시 하기' 줄에도 별로 표시됩니다.
풀이 보기를 쓰면 기록이 남나요?
풀이 보기는 지금 단계를 처음 자리로 되돌려 최소 풀이를 천천히 보여 주기만 하고 기록은 남기지 않습니다. 다 보면 다시 처음 자리에서 직접 해 볼 수 있습니다.
지난 단계를 다시 할 수 있나요?
네, 판 아래 '다시 하기' 줄의 단계 글자를 누르면 그 단계부터 다시 합니다. 깬 단계와 지금 열린 가장 높은 단계가 나옵니다.
기둥을 눌러 맨 위 원판을 들고, 옮길 기둥을 누르면 놓입니다. 원판을 끌어다 놓아도 됩니다.
