하노이의 탑

하노이의 탑 온라인으로 하기

이 페이지 위쪽의 판은 브라우저에서 바로 돌아가는 무료 하노이의 탑 게임입니다. 내려받을 것도, 가입할 것도 없습니다. 원반을 3개에서 15개 사이로 고른 뒤, 왼쪽 기둥의 원반 더미를 통째로 오른쪽 기둥으로 옮기세요.

• 휴대폰·태블릿: 기둥을 누르면 맨 위 원반이 들리고, 다른 기둥을 누르면 놓입니다.
• 마우스: 원반을 끌어다 옮기거나, 한 기둥을 클릭한 다음 다른 기둥을 클릭합니다.
• 키보드: ←와 →로 기둥을 고르고, ↑로 들고 ↓로 놓습니다. 1, 2, 3은 A, B, C 기둥으로 바로 가고, Esc는 원반을 되돌려 놓습니다.

실수해도 괜찮습니다. 되돌리기는 마지막 이동을 취소하고, 다시 시작은 같은 개수로 처음부터 시작하며, 힌트는 가장 짧은 풀이가 다음에 옮길 원반을 들어 올리고 어디로 가는지 알려 줍니다. 한 수는 그 수를 대신 둡니다. 그냥 지켜보고 싶다면 자동으로 풀기가 처음부터만이 아니라 판이 지금 어떤 상태든 그 자리에서부터 끝까지 풀어 줍니다.

첫 수를 두기 전에는 아무것도 세지 않습니다. 첫 이동 뒤에 패널에 다음이 나타납니다.

• 이동 수, 타이머, 그리고 완벽한 게임에 비한 내 게임의 비율인 효율 점수
• 아직 최적 경로 위에 있는지, 아니면 몇 번이나 벗어났는지

판 아래의 타임라인은 게임 전체를 기록합니다. 이전의 어느 배치로든 돌아갈 수 있고, 0.5×, 1×, 2×, 4× 속도로 다시 볼 수도 있습니다. 같은 속도 설정이 자동 풀이의 빠르기도 정합니다. 집중 모드는 기둥만 남기고 모두 치우며, 페이지는 마지막으로 한 원반 개수를 기억합니다. 게임을 끝내면 결과 화면이 내 이동 수를 최솟값과 비교하고 원반을 하나 더 늘려 보라고 권합니다.

하노이의 탑이라는 퍼즐

하노이의 탑은 기둥 세 개와, 그중 하나에 쌓인 크기가 서로 다른 원반 더미로 시작합니다. 맨 아래가 가장 큰 원반입니다. 목표는 다음 세 가지 규칙을 지키며 더미 전체를 다른 기둥으로 옮기는 것입니다.

1. 한 번에 원반 하나만 옮깁니다.
2. 기둥의 맨 위 원반만 옮길 수 있습니다.
3. 큰 원반을 작은 원반 위에 놓을 수 없습니다.

퍼즐은 이것이 전부이고, 1분이면 익힙니다. 어렵게 만드는 것은 세 번째 규칙입니다. 아래 원반들이 움직이는 동안 위의 원반은 놓아도 되는 어딘가에서 기다려야 하는데, 기둥이 셋뿐이라 자리가 늘 빠듯합니다. 하노이의 탑 게임 방법에서 규칙을 그림으로 보고 연습판과 풀이 예시로 익혀 보세요.

프랑스의 수학자 에두아르 뤼카가 1883년에 이 퍼즐을 발표했습니다. 이듬해 퍼즐을 소개한 잡지 기사가 지금은 유명해진 전설을 덧붙였습니다. 브라만 사제들이 황금 원반 64개를 다 옮기면 세상이 끝난다는 이야기입니다. 1초에 한 번씩 옮기면 약 5,850억 년이 걸립니다.

최소 이동 횟수와 2ⁿ − 1 공식

원반이 n개인 하노이의 탑의 최소 이동 횟수는 2ⁿ − 1이며, 2^n − 1로 쓰기도 합니다. 원반 3개는 7번, 4개는 15번, 5개는 최소 31번이 필요합니다. 이는 기록이 아니라 증명된 하한입니다. 어떤 개수에서도 이보다 짧은 풀이는 없으며, 판의 효율 점수도 바로 이 숫자와 비교합니다.

공식 뒤에 있는 식

이 식은 규칙에서 곧바로 나옵니다. 가장 큰 원반을 옮기려면 먼저 그 위의 n − 1개를 보조 기둥에 쌓아 두어야 하고, 그다음 큰 원반이 건너가며, 마지막으로 그 원반들이 다시 위로 올라옵니다. 이 모든 일을 하는 최소 이동 횟수를 T(n)이라 하면

T(n) = 2·T(n − 1) + 1, 그리고 T(0) = 0입니다. 원반이 없으면 이동도 없습니다.

각 개수의 비용은 한 개 적을 때의 두 배에 1을 더한 값입니다. 1, 3, 7, 15, 31, 63. 모두 2의 거듭제곱보다 1 작은 수이고, 여기서 닫힌 형태 T(n) = 2ⁿ − 1이 나옵니다. 2ⁿ − 1이 최소라는 증명은 이 주장의 두 부분, 곧 그만큼이면 항상 충분하다는 것과 그보다 적게는 불가능하다는 것을 차례로 다룹니다. 최소 이동 횟수 계산기는 64개까지 어떤 개수든 정확한 횟수를 알려 줍니다.

원반 개수별 최소 이동 횟수

각 개수에서 모든 이동을 목록으로 보여 주고 판에서 재생하는 전체 풀이로 넘어갈 수 있습니다. 여기서 할 수 있는 가장 큰 게임은 원반 15개, 곧 32,767번입니다. 원반이 하나 늘 때마다 게임 길이는 두 배에 한 번을 더한 만큼이 됩니다.

하노이의 탑 알고리즘과 재귀

위의 식은 지시문으로 읽으면 그대로 알고리즘입니다. 원반 n개를 출발 기둥에서 목표 기둥으로 옮기려면

1. n − 1개를 출발 기둥에서 보조 기둥으로 옮깁니다.
2. 가장 큰 원반을 출발 기둥에서 목표 기둥으로 옮깁니다.
3. n − 1개를 보조 기둥에서 목표 기둥으로 옮깁니다.

1단계와 3단계는 원반이 하나 적은 같은 문제이므로, 알고리즘은 자기 자신을 호출해 이를 풀고, 옮길 원반이 없는 호출은 그냥 돌아옵니다. 이것이 하노이의 탑 재귀의 전부이며, 거의 모든 컴퓨터 과학 수업이 이 퍼즐로 재귀를 가르치는 이유입니다. 요령은 모든 이동을 한꺼번에 떠올리려 하지 않는 것입니다. 더 작은 호출이 제 일을 해낼 거라 믿으면, 세 단계가 곧 풀이 전체입니다.

알고리즘은 정확히 2ⁿ − 1번 이동하므로 실행 시간은 O(2ⁿ)이고, 이보다 빠를 수는 없습니다. 그 이동 하나하나를 모두 해야 하기 때문입니다. 반면 메모리는 O(n)만 씁니다. 하노이의 탑 알고리즘 페이지는 움직이는 판 옆에서 코드를 한 줄씩 실행하며 호출 트리를 그려 가고, 반복문 해법은 규칙 두 개와 반복문 하나로 같은 이동을 만들어 냅니다.

Python, Java 등으로 짜는 하노이의 탑

세 단계는 거의 그대로 코드가 됩니다. Python으로 짠 하노이의 탑은 일곱 줄짜리 함수입니다. 원반 0개에 대한 기저 사례, 재귀 호출 두 번, 그리고 그 사이에서 이동을 출력하는 한 줄이 전부입니다. Java로 짠 하노이의 탑은 같은 메서드를 클래스 안에 넣은 것으로, 원반 64개의 횟수가 왜 long에 들어가지 않는지도 알 수 있습니다. 그 밖에 C, C++, C#, JavaScript로 된 완전한 프로그램도 있습니다.

모든 코드는 실제로 실행해 그 출력을 이 사이트의 해답기와 대조했고, 문법 설명이 아니라 각 줄이 왜 있는지를 풀어 주는 줄별 해설이 붙어 있습니다.

더 즐기고 배우는 방법

기둥 세 개와 가득 쌓인 더미가 쉬워졌다면 더 해 볼 것이 있습니다.

• 오늘의 도전 — 모두에게 같은 흐트러진 배치 하나. 협정 세계시 자정에 새로 바뀝니다. 해답기 없이 풀어 연속 기록을 이어 가세요.
• 해답기 — 어떤 올바른 배치에서든 가장 짧은 풀이의 모든 수를 보여 줍니다. 이 판에서 막힌 배치에서도 됩니다.
• 공략법 — 모든 크기 뒤에서 되풀이되는 단 하나의 생각과, 미리 계획하지 않아도 다음 수를 알려 주는 규칙.
• 변형 — 기둥 셋 대신 넷, 원반이 한 방향으로만 도는 고리, 두 색으로 나누기, 무작위 시작 배치.
• 선생님을 위해 — 45분 수업안, 답안이 있는 인쇄용 활동지, 강의 페이지에 넣을 수 있는 판.

자주 묻는 질문

하노이의 탑이란 무엇인가요?

하노이의 탑은 기둥 세 개와 크기가 서로 다른 원반 더미로 하는 퍼즐입니다. 더미 전체를 한 기둥에서 다른 기둥으로 옮기는데, 한 번에 원반 하나씩만 옮길 수 있고 큰 원반을 작은 원반 위에 놓을 수 없습니다. 프랑스의 수학자 에두아르 뤼카가 1883년에 발표했습니다.

하노이의 탑을 온라인에서 무료로 할 수 있나요?

네. 이 페이지의 판은 무료이고, 휴대폰·태블릿·컴퓨터의 최신 브라우저 어디서나 돌아가며, 내려받기나 계정이 필요 없습니다. 마지막으로 한 원반 개수와 최고 기록은 서버가 아니라 내 브라우저에 저장됩니다.

하노이의 탑의 최소 이동 횟수는 몇 번인가요?

원반 n개의 완벽한 게임은 2ⁿ − 1번입니다. 원반 3개는 7번, 5개는 31번, 15개는 32,767번입니다. 이보다 짧은 풀이는 없으므로 이 숫자는 목표가 아니라 넘을 수 없는 하한입니다.

하노이의 탑은 어떻게 푸나요?

모든 풀이는 같은 생각의 반복입니다. 원반 n개의 더미를 목표 기둥으로 옮기려면, 먼저 위의 n − 1개를 보조 기둥으로 치우고, 가장 큰 원반을 건너보낸 뒤, 그 n − 1개를 다시 그 위로 가져옵니다. 더 작은 더미도 똑같은 규칙을 따르므로 방법 하나로 모든 크기를 풀 수 있습니다.

다음 수를 바로 아는 요령이 있나요?

있습니다. 홀수 번째 이동에서는 가장 작은 원반을 정해진 방향으로 한 기둥씩 옮깁니다. 원반 개수가 홀수면 왼쪽, 짝수면 오른쪽이고 끝에 닿으면 반대편으로 넘어갑니다. 그래서 원반이 3개면 첫 수가 A에서 C로 넘어갑니다. 짝수 번째 이동에서는 가장 작은 원반을 건드리지 않는 유일한 올바른 수를 둡니다. 이 둘을 번갈아 하면 아무 계획 없이도 완벽한 게임이 됩니다.

여기서는 원반 몇 개로 할 수 있나요?

원반 3개부터 15개까지입니다. 3개로 시작해 풀이의 모양을 익히고, 그다음부터 하나씩 늘려 보세요. 원반이 하나 늘 때마다 할 일이 대략 두 배가 됩니다.

이동을 되돌리거나 게임을 다시 볼 수 있나요?

네. 되돌리기 버튼이 있고, 모든 게임에 전체 타임라인이 남습니다. 이전 어느 시점으로 돌아가면 판이 그때의 상태를 그대로 보여 주고, 네 가지 속도로 게임을 재생해 어디서 최적 경로를 벗어났는지 확인할 수 있습니다.