하노이 탑 소개
하노이 탑은 세 개의 기둥과 크기가 다른 원반들로 이루어진 퍼즐입니다. 왼쪽 기둥에 쌓인 원반 전부를 오른쪽 기둥으로 옮기면 성공입니다.
규칙은 두 가지뿐입니다. 한 번에 원반 하나만 옮길 수 있고, 큰 원반을 작은 원반 위에 올릴 수 없습니다. 이 단순한 제약 때문에 원반이 하나 늘 때마다 필요한 이동 횟수가 두 배 가까이 늘어납니다.
원반 n개를 옮기는 최소 횟수는 2ⁿ-1번입니다. 4개면 15번, 6개면 63번이죠. 컴퓨터공학에서 재귀를 설명할 때 거의 반드시 등장하는 문제이기도 합니다.
조작 방법
| 조작 | 동작 |
|---|---|
| 기둥 클릭 (1회) | 맨 위 원반 선택 |
| 기둥 클릭 (2회) | 선택한 원반을 그 기둥으로 이동 |
| 같은 기둥 다시 클릭 | 선택 취소 |
더 잘하는 방법
- 핵심 아이디어는 '가장 큰 원반을 옮기려면 나머지 전부를 가운데 기둥으로 먼저 치워야 한다'입니다. 이 생각을 재귀적으로 반복하면 됩니다.
- 원반 개수가 짝수면 첫 수를 가운데 기둥으로, 홀수면 오른쪽 기둥으로 두는 것이 최단 경로의 시작입니다.
- 가장 작은 원반은 매 두 번째 수마다 반드시 움직입니다. 방향도 일정하니 리듬을 타면 실수가 줄어듭니다.
- 3개로 감을 잡은 뒤 4개, 5개로 늘려가세요. 원리는 완전히 같습니다.
자주 묻는 질문
원반 64개면 얼마나 걸리나요?
1초에 한 번씩 옮겨도 약 5,850억 년이 걸립니다. 전설 속의 '세상의 끝' 이야기가 여기서 나왔습니다.
최소 횟수보다 적게 풀 수 있나요?
없습니다. 2ⁿ-1은 수학적으로 증명된 하한입니다.
기록은 어디에 저장되나요
하노이 탑의 최고 기록은 여러분이 사용하는 브라우저 안에만 저장됩니다. 서버로 전송되지 않으므로 다른 기기에서는 보이지 않고, 브라우저의 사이트 데이터를 지우면 함께 삭제됩니다. 자세한 내용은 개인정보처리방침에서 확인하실 수 있습니다.