d라이브러리

인도의 어느 사원에는 탑이 있어요. 다이아몬드로 만든 기둥에 금으로 만든 큰 원판 64개를 크기순으로 차곡차곡 끼워 만든 탑이지요. 옆에는 빈 기둥 두 개가 나란히 늘어서 있어요. 이 사원의 승려들은 한 명씩 돌아가며 원판을 차례대로 다른 기둥으로 옮기지요.

승려들이 탑을 다른 기둥으로 완전히 옮길 때까지 걸리는 최소 시간은 얼마일까요? 단, 탑을 옮길 때는 아래와 같은 규칙을 따라야 해요.
 

이 문제는 ‘하노이의 탑’이라고 하는 유명한 전설에서 따온 거예요. 전설에 따르면, 탑을 모두 옮겼을 때 세상이 멸망한다고 해요. 세상의 멸망을 건 이 문제를 해결하려면 자신을 호출해서 사용하는 ‘재귀 알고리즘’이 필요해요.

자신을 호출한다고 하니 어렵죠? 조금 더 풀어 말하면, 알고리즘으로 문제를 해결할 때 어떤 특정 과정을 계속 반복해서 사용하는 거예요. 이해하기 쉽도록 하노이의 탑 문제로 재귀 알고리즘을 만들어 볼까요?

하노이의 탑과 같은 규칙으로, 원판 세 개만 옮긴다고 해 봐요(왼쪽 그림). 이 원판을 작은 것부터 차례로 A, B, C라고 할게요. 규칙에 따르면 가장 밑에 있는 C가 옆 기둥으로 가야 나머지 A, B를 위에 올릴 수 있어요. 그리고 A, B가 없어야 C가 이동할 수 있죠.



그렇기 때문에 A를 먼저 세 번째 기둥으로 보내고, B를 두 번째 기둥으로 보낸 뒤 다시 A를 B 위로 올리는 과정이 진행돼야 해요. 그 다음으로 C를 세 번째 기둥에 끼우고, A를 첫 번째 기둥의 빈자리로 보낸 뒤 B, A 순으로 C 위에 다시 쌓아요. 이렇게 모두 옮기려면 총 7번을 이동하게 되네요.

그럼 네 개를 옮길 경우에는 원판을 몇 번 이동해야 할까요? 일단 위의 세 개를 옮기는 데 총 7번이 필요해요. 그리고 가장 아래의 원판을 옮기는 데 1번, 다른 기둥으로 옮겨 놓았던 세 개의 원판을 가장 아래 원판 위로 보내는 데 다시 7번이 필요해요. 마찬가지 방법으로, 5개를 옮길 때는 네 개를 옮기는 15번에 한
개를 옮기는 1번을 더하고, 다시 네 개를 옮기는 15번을 더해서 계산하면 돼요.

즉 n개의 원판을 옮기려면 n-1개의 원판을 옮기는 데 들어가는 횟수를 두 번 더하고, 거기에 한 회를 더하면 되는 거지요. n-1개의 원판이 세 개의 기둥을 오가는 과정이 계속 반복되고요.

이런 식으로 반복되는 과정을 이용하면 2ⁿ-1이라는 식을 구할 수 있어요. 이처럼 재귀 알고리즘을 만들면 복잡해 보이는 문제도 간단하게 정리할 수 있답니다.

그렇다면 하노이의 탑을 모두 옮기는 데 필요한 횟수는 몇 번일까요? n이 64개니까 2의 64승에서 1을 빼면 되겠죠? 답은 1844경 6744조 737억 955만 1615번이랍니다. 1초에 하나씩 옮긴다 해도 5800억 년 이상이 걸리지요. 세상 멸망은 아직 한참 남았으니 다들 안심하세요.