홍라이프 계산기하노이의 탑 이동 횟수 계산기 쉽게 이해하기 — 개념과 원리
하노이의 탑은 기둥 세 개와 크기가 다른 원판 n개로 이루어진 퍼즐입니다. 큰 원판이 아래에 오도록 쌓인 탑 전체를 다른 기둥으로 옮기되, 한 번에 원판 하나만 움직이고 작은 원판 위에 큰 원판을 올려서는 안 됩니다. 이 계산기는 원판 n개를 옮기는 최소 이동 횟수와, 일정한 속도로 옮길 때 걸리는 시간을 구합니다. 재귀, 수학적 귀납법, 지수적 증가를 설명할 때 가장 많이 쓰이는 예입니다.
계산 방법
- 최소 이동 횟수: M(n) = 2ⁿ − 1입니다. 정수 연산으로 정확히 계산하므로 원판이 64개여도 모든 자릿수가 표시됩니다.
- 소요 시간: (2ⁿ − 1) × 한 번 옮기는 데 걸리는 초입니다. 1시간 미만은 분, 1년 미만은 일, 그 이상은 년(365.25일 기준)으로 보여 줍니다.
원리
원판 n개를 A에서 C로 옮기려면 가장 큰 원판이 언젠가 한 번은 움직여야 하고, 그 순간 나머지 n − 1개는 모두 B에 있어야 합니다. 따라서 n − 1개를 B로 옮기고, 가장 큰 원판을 한 번 옮긴 뒤, 다시 n − 1개를 그 위로 옮깁니다. 이로부터 점화식 M(n) = 2·M(n − 1) + 1, M(1) = 1이 나옵니다. 양변에 1을 더하면 M(n) + 1 = 2·(M(n − 1) + 1)이므로, M(n) + 1은 원판이 하나 늘 때마다 두 배가 되어 2ⁿ이 됩니다. 각 단계가 반드시 필요한 과정이므로 이보다 적은 횟수로는 풀 수 없다는 것도 함께 증명됩니다.
예제 풀이
- 입력값은 원판 10개, 한 번 옮기는 데 1초입니다.
- 2¹⁰ = 1024이므로 최소 이동 횟수는 1024 − 1 = 1023번입니다.
- 소요 시간은 1023 × 1초 = 1023초입니다.
- 1시간 미만이므로 분으로 바꾸면 1023 ÷ 60 = 17.05분입니다.
| 원판 수 | 최소 이동 횟수 |
|---|---|
| 2.5 | 7 |
| 5 | 31 |
| 7.5 | 255 |
| 10 | 1023 |
| 12.5 | 8191 |
| 15 | 32767 |
| 20 | 1048575 |
결과 해석
원판이 하나 늘 때마다 일의 양이 거의 두 배가 됩니다. 3개는 7번, 5개는 31번, 8개는 255번이지만 20개가 되면 1,048,575번으로 100만 번을 넘습니다. 전설 속 64개의 원판은 18,446,744,073,709,551,615번이 필요하여, 1초에 한 번씩 옮겨도 약 5,845억 년이 걸립니다. 지수 시간 알고리즘이 입력이 크지 않아 보여도 금세 쓸 수 없게 되는 이유가 바로 이것입니다.
흔한 실수
- 2ⁿ − 1이 아니라 2ⁿ으로 계산하는 경우입니다. 원판이 적을 때는 차이가 큽니다.
- 손이 빨라지면 증가 속도가 달라진다고 생각하지만, 시간이 비례해서 줄어들 뿐입니다.
- 들어 올리기와 내려놓기를 따로 세는 경우입니다. 원판 하나를 옮기는 것이 1번입니다.
자주 묻는 질문
원판 3개, 4개, 5개의 최소 이동 횟수는 얼마인가요?
2ⁿ − 1에 따라 각각 7번, 15번, 31번입니다.
목표 기둥이 어느 쪽이든 횟수가 같나요?
같습니다. 나머지 두 기둥 중 어느 쪽으로 옮겨도 2ⁿ − 1번이며, 가장 작은 원판의 첫 이동 방향만 달라집니다.
재귀를 쓰지 않고 푸는 방법도 있나요?
있습니다. 가장 작은 원판을 정해진 방향으로 한 칸씩 돌리는 동작과, 가장 작은 원판을 건드리지 않는 유일한 합법적 이동을 번갈아 하면 됩니다.
출처: R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1장 · Édouard Lucas, Récréations mathématiques, 3권 (1893)