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