2ⁿ−1 · 하노이 탑
하노이 탑
기둥 세 개와 크기가 다른 원판들이 있습니다. 한 번에 한 장씩만 옮길 수 있고, 큰 원판은 작은 원판 위에 올릴 수 없어요. 원판 3개를 옆 기둥으로 옮기려면 최소 몇 번이면 될까요?
다 옮기는 날 세상이 끝난다는, 64개 황금 원판의 전설
먼저 직접 생각해 보세요
먼저 결과를 예상해 보세요. 값을 하나씩 바꾸면서 예상과 무엇이 다른지 살펴봅시다.
규칙: 한 번에 한 장 · 큰 원판은 작은 원판 위에 못 올려요. 기둥을 탭해 원판을 집고, 다른 기둥을 탭해 내려놓으세요.
기둥을 탭해 맨 위 원판을 집어 보세요.
생각을 정리한 뒤 해설 읽기
하노이 탑은 옮기는 문제가 아니라 쪼개는 문제다.
이 질문이 왜 필요할까요?
하노이 탑은 1883년 프랑스 수학자 에두아르 뤼카가 만든 퍼즐입니다. '브라만 사원의 승려들이 64개의 황금 원판을 옮기고 있고, 다 옮기는 날 세상이 끝난다'는 이야기도 함께 붙였는데, 이건 뤼카가 퍼즐을 위해 지어낸 전설이에요.
이 퍼즐이 140년 넘게 살아남은 이유는 답이 아니라 푸는 방법에 있습니다. 원판 n개를 통째로 옮길 방법은 없어요. 하지만 '위의 n−1개를 먼저 치운다'고 생각하는 순간, 큰 문제가 한 단계 작은 같은 문제로 바뀝니다.
이렇게 문제를 자기 자신의 작은 버전으로 쪼개는 사고를 재귀라고 부릅니다. 컴퓨터가 큰 데이터를 정렬하고 검색하는 방법의 뼈대가 바로 이 사고예요. 하노이 탑은 재귀를 손으로 만져보는 가장 오래된 실험실입니다.
같은 생각을 다른 말로 읽어 봅시다
큰 원판을 옮기려면 그 위의 작은 원판들이 먼저 자리를 비워야 합니다. 작은 문제를 풀고, 큰 원판 하나를 옮기고, 같은 크기의 작은 문제를 다시 푸는 구조가 반복됩니다.
원판 하나는 한 번 옮기면 됩니다. 원판 두 개는 작은 것 이동, 큰 것 이동, 작은 것 이동으로 세 번입니다. T(n)=2T(n−1)+1이라는 식은 이 세 단계의 작업량을 적은 것입니다.
n개를 옮기는 법은 몰라도, n−1개를 옮길 줄 알면 끝난다.
위의 n−1개를 보조 기둥으로 치우고, 맨 아래 한 장을 옮기고, n−1개를 다시 위에 얹으면 됩니다. 큰 문제를 직접 푸는 대신 작은 문제에게 미루는 것 — 이 미루기가 재귀의 전부예요.
2배가 반복되면 인간의 직관은 반드시 진다.
원판 하나에 2배씩. 열 개면 천 번, 스무 개면 백만 번, 64개면 우주 나이의 40배입니다. 지수의 폭발을 몸으로 느껴본 사람만 '금방 되겠지'라는 함정을 피할 수 있어요.
이제 정의와 조건을 함께 읽습니다
기둥은 세 개이며 한 번에 원판 하나만 옮기고, 큰 원판을 작은 원판 위에 둘 수 없다는 규칙입니다.
실험에서 발견한 규칙을 수식으로 옮겨 봅시다. n개를 옮기는 최소 횟수를 M(n)이라 부르면, 방금 손으로 겪은 '치우고, 옮기고, 다시 얹기'가 그대로 식이 됩니다.
공식 해부 — 손으로 한 세 동작이 그대로 식이 된다
= + +
점화식 (쪼개기)
n개의 답은 n−1개의 답 두 번에 1을 더한 것입니다. 큰 문제가 작은 문제로 쪼개지는 순간이에요.
닫힌 식
점화식을 끝까지 풀면 이 한 줄이 됩니다. 1, 3, 7, 15, 31, … 모두 2의 거듭제곱보다 1 작은 수예요.
64개의 시간
1초에 한 장씩 옮겨도 우주 나이(약 138억 년)의 40배가 넘습니다. 전설이 '세상이 끝난다'고 말한 이유예요.
여기서 한 번 더 구분해 볼까요?
원판이 하나 늘면 몇 번쯤 더 옮기면 된다.
덧셈이 아니라 곱셈으로 늘어납니다. 원판이 하나 늘 때마다 최소 횟수는 약 2배가 돼요. n개를 옮기려면 위의 n−1개를 두 번 옮겨야 하기 때문입니다. 3개는 7번이지만 10개는 벌써 1,023번이에요.
64개쯤이야 빠르게 하면 금방 끝난다.
1초에 한 장씩 쉬지 않고 옮겨도 약 5,849억 년이 걸립니다. 우주의 나이(약 138억 년)의 40배가 넘어요. 지수의 폭발은 부지런함으로 이길 수 없습니다.
다른 질문에서는 어떻게 쓰일까요?
분할 정복 알고리즘
컴퓨터가 100만 개의 데이터를 정렬할 때, 절반씩 쪼개 작은 정렬로 만든 뒤 합칩니다(합병 정렬). '작은 같은 문제에게 미루기'라는 하노이 탑의 사고가 그대로예요.
프로그래밍의 첫 재귀
전 세계 프로그래밍 수업에서 재귀 함수를 처음 가르칠 때 쓰는 단골 예제가 하노이 탑입니다. 함수가 자기 자신을 부르는 구조를 눈으로 보여주기 때문이에요.
백업 테이프 로테이션
서버 백업을 며칠 주기로 돌려쓸지 정하는 고전 기법의 이름이 '하노이 탑 방식'입니다. 원판이 움직이는 주기(1번 원판은 2번마다, 2번 원판은 4번마다)를 그대로 빌렸어요.
심리학의 문제해결 실험
인지심리학과 뇌과학은 사람의 계획 능력을 측정할 때 하노이 탑을 씁니다. 몇 수 앞을 내다보며 중간 목표를 세우는 힘이 그대로 드러나는 과제이기 때문이에요.
이번에는 내 말로 설명해 보세요
왜 작은 문제를 두 번 푸는 항이 생기나요?
생각한 뒤 설명 확인하기
큰 원판의 길을 비우는 과정과, 옮긴 큰 원판 위에 작은 원판들을 다시 쌓는 과정이 각각 필요하기 때문입니다.
계산과 개념을 문제로 확인하기 (4)
문제 완료 0 / 4
1. 원판 4개를 옮기는 최소 횟수는 몇 번일까요?
2. 최소 횟수가 M(n) = 2M(n−1) + 1인 이유는 무엇일까요?
3. 원판 5개를 옮기는 최소 횟수는 몇 번일까요?
4. 원판이 하나 늘어나면 최소 이동 횟수는 어떻게 될까요?
다음에는 어떤 질문을 해볼까요?
이전 개념
다음 개념으로 연결
관련 실험실
관련 실험실