하노이의 탑은 프로그래밍에서 “재귀”를 배울 때 거의 반드시 나오는 소재예요. 손으로 풀면 수백 수나 걸리는데, 프로그램으로 만들면 몇 줄로 쓸 수 있어요. 그 원리를 차례로 살펴봐요. 기둥은 왼쪽·가운데·오른쪽이고, 원판에는 작은 것부터 차례로 1, 2, 3…번을 붙여요.

재귀란

재귀란 어떤 문제를 푸는 순서 안에서 같은 순서를 더 작은 문제에 쓰는 것이에요. 계속 작게 만들다 보면 언젠가 바로 답을 아는 문제(원판이 0개면 아무것도 하지 않는다 등)에 이르기 때문에, 거기서 멈춰요.

하노이의 탑을 재귀로 생각하기

원판 n개의 탑을 왼쪽에서 오른쪽으로 옮기는 것을 생각해 봐요.

  1. 위의 n−1개를 왼쪽에서 가운데로 옮긴다.
  2. 가장 큰 원판 n을 왼쪽에서 오른쪽으로 움직인다.
  3. 가운데의 n−1개를 오른쪽으로 옮긴다.

1과 3은 “원판 n−1개의 탑을 옮기는” 문제로, 원래 문제와 같은 모양이에요. 다른 것은 어느 기둥에서 어느 기둥으로 옮기느냐뿐이에요. 그래서 “원판 n개를 어떤 기둥에서 다른 기둥으로, 남은 기둥을 써서 옮긴다”라는 순서를 하나 만들면, 그 안에서 자기 자신을 부를 수 있어요.

의사 코드

순서 hanoi(n, 옮길 곳의 출발, 옮길 곳의 도착, 쓰는 기둥):
    만약 n이 0이면, 아무것도 하지 않고 끝낸다
    hanoi(n − 1, 옮길 곳의 출발, 쓰는 기둥, 옮길 곳의 도착)    … 위의 n−1개를 치운다
    원판 n을 출발 기둥에서 도착 기둥으로 움직인다
    hanoi(n − 1, 쓰는 기둥, 옮길 곳의 도착, 옮길 곳의 출발)    … n−1개를 되돌린다

hanoi(3, 왼쪽, 오른쪽, 가운데)로 원판 3개를 왼쪽에서 오른쪽으로 옮기는 순서가 나온다

이것만으로 원판이 몇 개든 최소 수의 순서가 나와요. 실제로 움직이는 Python이나 C 언어 코드는 Python·C 언어로 하노이의 탑 풀기에서 소개해요.

호출이 퍼지는 모양

원판이 3개일 때 hanoi가 어떻게 호출되는지 적어 보면 다음과 같은 나무 모양이 돼요. 들여쓰기가 깊을수록 안쪽 호출이에요.

hanoi(3, 왼쪽→오른쪽)
├─ hanoi(2, 왼쪽→가운데)
│   ├─ hanoi(1, 왼쪽→오른쪽)     … 1을 오른쪽으로
│   ├─ 2를 가운데로
│   └─ hanoi(1, 오른쪽→가운데)   … 1을 가운데로
├─ 3을 오른쪽으로
└─ hanoi(2, 가운데→오른쪽)
    ├─ hanoi(1, 가운데→왼쪽)   … 1을 왼쪽으로
    ├─ 2를 오른쪽으로
    └─ hanoi(1, 왼쪽→오른쪽)     … 1을 오른쪽으로

위에서부터 차례로 읽은 “움직인다”의 나열이 그대로 7수의 답이에요. 한 번의 호출이 안쪽에서 두 번의 호출을 낳기 때문에, 원판이 1개 늘 때마다 일은 거의 2배가 돼요.

계산량

알아볼 것원판이 n개일 때
움직이는 횟수(수)2ⁿ−1번
hanoi를 호출하는 횟수(원판 0개의 호출도 센다)2ⁿ⁺¹−1번
호출의 깊이(동시에 기억해 둘 양)n+1단

수가 2ⁿ−1번이 되는 이유는 최소 수 공식에서 증명해요. 걸리는 시간은 원판 개수에 대해 지수함수적으로 늘고(O(2ⁿ)), 기억해 둘 양은 개수에 비례할 뿐이에요(O(n)). 수 자체가 2ⁿ−1번이나 있으니, 아무리 궁리해도 순서를 모두 적어 내려면 이만큼의 시간이 걸려요.

재귀를 쓰지 않는 풀이

재귀를 쓰지 않고 반복만으로 푸는 방법도 있어요. 푸는 법 기사에서 소개한, 손으로 풀 때의 순서 그대로예요.

순서 hanoi_loop(n):
    1의 방향을 정한다(n이 홀수면 왼쪽→오른쪽→가운데, 짝수면 왼쪽→가운데→오른쪽 순서)
    수 = 1, 2, 3, … , 2ⁿ − 1에 대해 되풀이한다:
        수가 홀수면, 원판 1을 정한 방향으로 옆 기둥으로 하나 움직인다
        수가 짝수면, 1이 놓여 있지 않은 두 기둥의 맨 위끼리 비교해서
                       작은 쪽을 큰 쪽(또는 빈 기둥)으로 움직인다

재귀처럼 호출을 기억해 둘 필요가 없어서, 쓰는 기억량이 아주 적어도 돼요.

이진수로 몇 번째 수든 바로 구하기

더 나아가, 몇 번째 수에서 무엇을 할지를 그때까지의 수를 따라가지 않고 바로 구하는 방법도 있어요. 기둥을 0·1·2번으로 부르고, m번째 수(1부터 센다)에 대해,

  • 움직일 원판은 m을 이진수로 썼을 때 끝에 이어지는 0의 개수+1번 원판.
  • 움직일 출발 기둥은 (m AND (m − 1))을 3으로 나눈 나머지.
  • 움직일 도착 기둥은 ((m OR (m − 1)) + 1)을 3으로 나눈 나머지.

AND와 OR는 이진수의 자리마다 하는 “그리고”와 “또는” 계산이에요. 예를 들어 m = 4(이진수로 100)라면, 끝의 0이 2개이니 원판은 3번, 출발은 (4 AND 3) = 0이니 기둥 0, 도착은 ((4 OR 3) + 1) = 8을 3으로 나눈 나머지인 기둥 2예요.

이 식으로 나오는 순서는, 원판이 홀수 개면 기둥 0에서 기둥 2로, 짝수 개면 기둥 0에서 기둥 1로 옮기는 순서가 돼요. 짝수 개에서 기둥 2로 옮기고 싶을 때는 기둥 1과 기둥 2를 바꿔서 읽어요. 수와 이진수의 이런 연결은 규칙성 기사에서 자세히 소개해요.