세 개의 기둥, 그리고 크기가 다른 여러 개의 원반. 단순해 보이는 이 구성품으로 이루어진 ‘하노이의 탑’은 단순한 퍼즐을 넘어, 컴퓨터 과학의 핵심 원리를 담고 있는 아주 우아하고 아름다운 문제입니다. 어쩌면 이 퍼즐을 풀다가 ‘이건 절대 못 풀어!’라며 좌절한 경험이 있으실지도 모르겠습니다.
‘64개의 원반을 모두 옮기면 세상의 종말이 온다’는 신비로운 전설까지 품고 있는 이 퍼즐. 하지만 너무 겁먹을 필요는 없습니다. 결론부터 말씀드릴게요. 이 퍼즐을 푸는 열쇠는 원반 하나하나를 옮기는 데 있지 않습니다. 바로 ‘원반 덩어리’를 하나의 그룹으로 생각하고 움직이는, 아주 간단한 생각의 전환에 있습니다.
세상에서 가장 간단한 세 가지 규칙
하노이의 탑이 매력적인 이유는, 그 목표는 명확하고 규칙은 놀라울 만큼 간단하기 때문입니다. 우리의 목표는 첫 번째 기둥(A)에 꽂혀있는 모든 원반을 세 번째 기둥(C)으로 똑같은 순서 그대로 옮기는 것입니다. 이때, 반드시 지켜야 할 규칙은 딱 세 가지뿐입니다.
첫째, 한 번에 오직 하나의 원반만 옮길 수 있습니다. 둘째, 절대로 큰 원반을 작은 원반 위에 올릴 수 없습니다. 셋째, 원반을 옮길 때는 반드시 세 개의 기둥 중 하나만 사용해야 합니다. 이 세 가지 간단한 제약 조건이 바로 이 퍼즐을 흥미롭게 만드는 모든 것입니다.
가장 큰 원반을 옮기려면?
자, 그럼 이 퍼즐을 어떻게 해결해야 할까요? 8개의 원반을 한 번에 생각하면 머리가 아파옵니다. 대신, 딱 3개의 원반만 있다고 상상해 봅시다. 우리의 최종 목표는 가장 큰 3번 원반을 A에서 C로 옮기는 것입니다. 그러려면 어떻게 해야 할까요? 맞습니다. 3번 원반 위에 있던 1번과 2번 원반이 길을 비켜줘야 합니다.
3번 원반이 C로 가기 위해서는, 그보다 작은 1번과 2번 원반이 모두 중간 기둥(B)에 미리 도착해 있어야만 합니다. 즉, ‘3개의 원반을 A에서 C로 옮기는 문제’는, ‘2개의 원반을 A에서 B로 옮기는 문제’와 ‘가장 큰 원반 하나를 A에서 C로 옮기는 문제’로 나눌 수 있습니다. 이 간단한 생각의 전환이 모든 문제 해결의 시작입니다.
스스로를 부르는 마법, 재귀 함수
바로 이 지점에서 컴퓨터 과학의 아주 중요한 개념인 ‘재귀(Recursion)’가 등장합니다. 재귀란, 큰 문제를 해결하기 위해 그 문제와 똑같은 형태의 더 작은 문제를 풀어내는 방식을 말합니다. 마치 큰 양파를 까기 위해 작은 양파 껍질을 계속해서 벗겨내는 것과 같죠.
하노이의 탑 해법은 재귀의 원리를 완벽하게 보여줍니다. ‘N개의 원반을 A에서 C로 옮기기’라는 큰 문제는 다음과 같은 세 단계로 나눌 수 있습니다. 1) N-1개의 작은 원반 덩어리를 A에서 B로 옮긴다. 2) 남은 가장 큰 원반 하나를 A에서 C로 옮긴다. 3) B에 있던 N-1개의 원반 덩어리를 다시 C로 옮긴다. 즉, N개의 원반을 옮기는 문제를, (N-1)개의 원반을 옮기는 작은 문제 두 개로 나누어 해결하는 것입니다.
최소 이동 횟수, 공식이 있다고요?
이 재귀적인 해법을 따르면, 우리는 항상 가장 적은 횟수로 원반을 옮길 수 있습니다. 그리고 놀랍게도, 여기에는 아주 간단한 수학 공식이 존재합니다. 원반의 개수를 n이라고 할 때, 최소 이동 횟수는 ‘2의 n제곱 - 1’ (2^n - 1) 입니다.
예를 들어, 원반이 3개일 때는 2³ - 1 = 7번, 4개일 때는 2⁴ - 1 = 15번의 이동이 필요합니다. 그렇다면 전설에 나오는 64개의 원반은 어떨까요? 무려 18,446,744,073,709,551,615번의 이동이 필요합니다. 1초에 한 번씩 원반을 옮겨도 5,849억 년이 넘게 걸리는, 그야말로 우주의 종말을 떠올리게 하는 숫자입니다.
단순한 퍼즐 그 이상의 의미
하노이의 탑은 단순한 시간 때우기용 장난감이 아닙니다. 복잡하고 거대한 문제를 더 작고 다루기 쉬운 똑같은 형태의 문제로 나누어 해결하는 ‘분할 정복(Divide and Conquer)’이라는 아주 중요한 문제 해결 전략의 가장 대표적인 예시입니다.
컴퓨터가 수많은 파일 속에서 특정 단어를 찾아내거나, 복잡한 경로를 계산하는 등 수많은 알고리즘이 바로 이 재귀적인 사고방식을 기반으로 만들어졌습니다. 하노이의 탑을 이해하는 것은, 컴퓨터처럼 생각하는 법을 배우는 첫걸음과도 같습니다.
자주 묻는 질문 (FAQ)
Q. 왜 이름이 ‘하노이의 탑’인가요?
A. 1883년 프랑스의 수학자 에두아르 뤼카가 이 퍼즐을 유럽에 소개하면서, 베트남의 도시 ‘하노이’에 있는 신비로운 전설을 덧붙여 마케팅했기 때문이라고 알려져 있습니다. 실제 베트남과는 큰 관련이 없을 수 있습니다.
Q. 기둥이 4개라면 더 쉬워지나요?
A. 네, 훨씬 더 쉬워집니다. 사용할 수 있는 중간 기둥이 하나 더 늘어나기 때문에, 원반을 옮길 수 있는 경우의 수가 많아져 최소 이동 횟수가 비약적으로 줄어듭니다.
Q. 원반이 2개일 때는 어떻게 하나요?
A. 규칙은 똑같습니다. 1번 원반을 A에서 B로, 2번 원반을 A에서 C로, 다시 1번 원반을 B에서 C로 옮기면 2² - 1 = 3번 만에 해결됩니다.
추가 정보 및 도움이 되는 자료
- 재귀함수의 개념과 하노이의 탑 - YouTube
재귀함수의 기본 개념과 하노이탑 문제를 재귀적으로 해결하는 방법을 쉽게 설명하는 영상입니다. - [알고리즘/C++]하노이탑알고리즘 - MY블로그 - 티스토리
하노이탑 문제의 규칙과 재귀 함수를 이용한 C++ 구현 예제를 통해 문제 해결 과정을 상세히 설명합니다. - 하노이의 탑(The Tower of Hanoi) 을 구현해보자! : 재귀의 원리 - Velog
하노이탑 문제를 재귀적으로 접근하는 방법과 재귀 호출 구조, 문제 해결의 핵심 패턴을 쉽게 이해할 수 있도록 설명합니다. - '하노이의 탑' 이해하기 - Parkito's on the way
하노이탑 문제를 수학적 재귀식과 프로그래밍 구현 관점에서 깊이 있게 분석한 글입니다. - '하노이의 탑' 이해하기 (feat. 재귀 함수) - mgyo - 티스토리
재귀 함수를 통한 하노이탑 해결 과정을 단계별로 설명하며, 기초부터 확장까지 큰 그림을 보여줍니다.