하노이의 탑 계산기

그게 실제로 얼마나 긴 시간인가

위의 수치는 정확하지만, 그 자체로는 거의 아무것도 알려 주지 않습니다. 수십억을 넘어가면 아주 큰 수는 서로 비슷해 보입니다. 이 계산이 정말로 하는 일은 말로 듣는 것보다 보는 편이 빠릅니다. 원반이 하나 늘 때마다 일이 두 배가 되므로, 원반 개수로 균등한 자는 시간으로는 곱해지는 자가 됩니다. 그래서 커피 한 잔의 휴식(원반 10개, 17분)에서 우주의 나이(원반 59개)까지의 거리는 약 쉰 걸음밖에 되지 않습니다.

• 원반 1개 — 1번의 이동 — 1초: 1초에 처음으로 이르는 개수입니다.
• 원반 6개 — 63번의 이동 — 1분: 1분에 처음으로 이르는 개수입니다.
• 원반 12개 — 4,095번의 이동 — 1시간: 1시간에 처음으로 이르는 개수입니다.
• 원반 17개 — 131,071번의 이동 — 1일: 하루에 처음으로 이르는 개수입니다.
• 원반 25개 — 33,554,431번의 이동 — 1년: 1년에 처음으로 이르는 개수입니다.
• 원반 32개 — 4,294,967,295번의 이동 — 136년: 사람의 한평생에 처음으로 이르는 개수입니다.
• 원반 38개 — 274,877,906,943번의 이동 — 8,710년: 기록된 역사 전체에 처음으로 이르는 개수입니다.
• 원반 59개 — 576,460,752,303,423,487번의 이동 — 183억 년: 우주의 나이에 처음으로 이르는 개수입니다.

왼쪽의 색칠된 구간이 여기서 실제로 플레이할 수 있는 전부입니다. 원반 11개면 긴 한 판이고, 25개면 쉬지 않고 옮겨도 1년이며, 59개면 우주의 나이를 넘어섭니다. 이 축 어디에서도 규칙은 달라지지 않습니다. 달라지는 것은 수뿐입니다.

공식

원반 n개의 완벽한 풀이는 정확히 2ⁿ − 1번입니다. 이것이 하노이의 탑 공식이고, 위 첨자를 쓸 수 없을 때는 2^n − 1로도 씁니다. 이것은 누군가가 세운 최고 기록이 아니라 증명된 하한입니다. 가장 큰 원반이 움직이려면 그보다 작은 원반이 모두 보조 기둥에 쌓여 비켜나 있어야 하고, 큰 원반이 건너간 뒤에는 모두 그 위로 돌아와야 합니다. 원반 n − 1개의 전체 옮기기 두 번에 한 번의 이동입니다.

T(n) = 2·T(n − 1) + 1, 출발점은 T(0) = 0입니다. 원반이 없으면 옮길 것도 없습니다.

1. 1위에 있는 n−1개의 원반을 보조 기둥으로 옮깁니다. 이 원반들이 비켜나기 전에는 아무것도 할 수 없습니다.

2. 2가장 큰 원반이 이제 자유롭고, 목표 기둥도 비어 있습니다. 한 번에 건너갑니다. 이 단계에 필요한 이동은 그것뿐입니다.

3. 3그 위에 n−1개의 원반을 다시 쌓습니다. 원반이 하나 적은 같은 문제이며, 끝까지 내려가면 한 번에 움직이는 원반 하나가 남습니다.

이를 풀어 쓰면 1, 3, 7, 15, 31, 63이 됩니다. 모두 앞의 수의 두 배에 1을 더한 값이고, 2의 거듭제곱보다 하나 작은 수들의 수열입니다. 원반을 하나 더할 때마다 일은 두 배를 조금 넘게 늘어나고, 그래서 이 퍼즐은 쉰 걸음도 되지 않아 커피 한 잔의 휴식에서 우주가 존재한 시간보다 긴 시간으로 건너갑니다.

같은 점화식이 이 퍼즐이 전산학 수업에서 유명한 이유이기도 합니다. 원반마다 일이 두 배가 되므로 재귀 해법의 실행 시간은 O(2ⁿ)입니다. 그 뒤에 더 영리한 알고리즘이 숨어 있는 것이 아닙니다. 이동 수 자체가 지수적이고, 모든 이동을 출력해야 하기 때문입니다. 반면 들지 않는 것은 메모리입니다. 재귀는 한 번에 원반 하나씩만 내려가므로 스택 프레임은 O(n)개, 원반마다 하나에 기저 사례로 하나입니다. 여기서 가장 큰 판은 16개, 전설은 65개입니다. 전체 유도와, 이것이 마스터 정리를 적용할 수 있는 점화식이 아닌 이유는 하노이의 탑 알고리즘 페이지에 있습니다.

원반 개수별 최소 이동 수

여기서 플레이할 수 있는 개수입니다. 난이도 구간은 판의 원반 개수 조절기 옆에 나오는 것과 같고, 각 개수에서 그것을 푸는 이동 목록으로 갈 수 있습니다.

판 너머

원반 15개를 넘어가면 이 퍼즐은 플레이하는 것이 아니라 계산하는 것이 됩니다. 수치는 여전히 정확합니다. 다만 사람의 한평생으로는 닿을 수 없을 뿐입니다.

이 수에는 이름이 있다

2의 거듭제곱보다 하나 작은 수는 메르센 수라고 하며 M_n = 2ⁿ − 1로 씁니다. 그러니 위 표의 모든 수치가 메르센 수이고, 하노이의 탑의 이동 수가 그 밖의 수가 되는 일은 없습니다. 메르센 수가 마침 소수일 때 그것을 메르센 소수라고 하며, 기록적인 소수를 찾는 탐색이 수십 년째 이 수들 위에서 돌아가고 있습니다. 2ⁿ − 1은 같은 크기의 임의의 수보다 소수 판정이 훨씬 싸기 때문입니다.

M_n이 소수가 되려면 n도 소수여야 하지만, 그것만으로는 충분하지 않습니다. 그 반례가 바로 여기서 플레이할 수 있는 판입니다. 11은 소수지만 그 2,047번은 소수가 아닙니다. 2,047 = 23 × 89 이기 때문입니다. 이 판의 개수 중 이동 수가 소수인 것은 원반 3, 5, 7 및 13개입니다. OEIS A000225가 전체 수열입니다.

원반 64개의 전설

이 퍼즐은 1883년에 판매를 시작했고, 1년도 지나지 않아 이야기가 붙었습니다. 베나레스의 한 사원에서 사제들이 세 개의 다이아몬드 바늘 사이로 64개의 황금 원반을 옮기고 있으며, 마지막 원반을 놓는 순간 세상이 끝난다는 이야기입니다. 계산해 보면 마음이 놓입니다. 원반 64개는 18,446,744,073,709,551,615번이고, 1초에 한 번씩 옮기면 5,850억 년으로, 지금 우주 나이의 약 마흔 배입니다.

자주 묻는 질문

하노이의 탑은 몇 번 옮겨야 하나요?

최소는 원반 n개에 2ⁿ − 1번입니다. 3개는 7번, 5개는 31번, 10개는 1,023번, 20개는 1,048,575번입니다. 원반이 하나 늘 때마다 합계는 두 배를 조금 넘게 늘어납니다. n개를 푼다는 것은 n − 1개를 두 번 풀고 그 사이에 한 번 옮긴다는 뜻이기 때문입니다.

왜 공식이 2ⁿ − 1인가요?

원반 n개를 옮기려면 먼저 위의 n − 1개를 비켜 놓고, 가장 큰 원반을 한 번 옮기고, 그 n − 1개를 다시 그 위로 올려야 합니다. 여기서 T(n) = 2·T(n−1) + 1, T(1) = 1이 나오고, 풀어 쓰면 1, 3, 7, 15, 31이 됩니다. 모두 앞의 값의 두 배에 1을 더한 값, 즉 정확히 2ⁿ − 1입니다.

하노이의 탑의 시간 복잡도는 얼마인가요?

O(2ⁿ)입니다. 원반마다 일이 두 배가 되므로 재귀 해법은 2ⁿ − 1번의 이동을 만들고, 어떤 알고리즘도 이를 이길 수 없습니다. 이동 자체를 만들어 내야 하고, 그 수가 그만큼이기 때문입니다. 공간은 O(n)뿐입니다. 재귀는 한 번에 원반 하나씩 내려가므로 동시에 스택에 있는 프레임은 많아야 n + 1개입니다. 그래서 원반 64개 호출은 스택보다 여러분의 인내심을 훨씬 먼저 바닥냅니다.

원반 64개는 얼마나 걸리나요?

원반 64개에는 18,446,744,073,709,551,615번의 이동이 필요합니다. 1초에 한 번씩 옮기면 5,850억 년으로, 지금 우주의 나이보다 훨씬 깁니다. 1884년에 이 퍼즐에 붙은 전설이 노린 것이 바로 그 점입니다.

2ⁿ − 1보다 짧은 해답이 있을 수 있나요?

없습니다. 2ⁿ − 1은 현재까지 알려진 최선이 아니라 증명된 하한입니다. 가장 큰 원반은 적어도 한 번은 움직여야 하고, 그러려면 그보다 작은 원반이 모두 그 위에서도, 목적지에서도 비켜나 있어야 합니다. 그래서 두 번의 부분 옮기기가 강제되고, 같은 논리가 끝까지 되풀이됩니다.

절반쯤 푼 판에도 계산기를 쓸 수 있나요?

이 페이지로는 안 됩니다. 2ⁿ − 1은 모든 원반이 한 기둥에서 시작한다고 전제합니다. 이미 중간까지 간 배치에서의 가장 짧은 해답은, 규칙에 맞는 어떤 배치에서든 최적 경로를 계산하는 해답기를 쓰세요. 해답기 열기 →