하노이의 탑 점화식: 원판 n개의 최소 이동 횟수가 2ⁿ−1인 이유

하노이의 탑은 크기가 서로 다른 원판을 세 기둥 사이에서 옮기는 퍼즐입니다. 규칙은 단순합니다. 한 번에 원판 하나만 옮기고, 큰 원판을 작은 원판 위에 올릴 수 없습니다. 출발 기둥에 크기순으로 쌓인 원판 n개를 목적 기둥으로 모두 옮기려면 최소 몇 번 움직여야 할까요? 고전적인 세 기둥 문제의 답은 2ⁿ−1번입니다.

이 공식은 가능한 순서를 몇 개 시험해 얻는 경험식이 아닙니다. 가장 큰 원판을 옮기려면 그 위의 n−1개를 먼저 비워야 하고, 큰 원판을 옮긴 뒤에는 n−1개를 다시 그 위로 쌓아야 합니다. 이 필수 구조가 T(n)=2T(n−1)+1이라는 점화식을 만들며, 점화식을 풀면 T(n)=2ⁿ−1이 나옵니다.

고전적인 세 기둥 하노이의 탑: T(0)=0, T(n)=2T(n−1)+1, 따라서 T(n)=2ⁿ−1

하노이의 탑 규칙부터 정확히 정리하기

1. 출발 기둥의 원판 n개를 목적 기둥으로 모두 옮깁니다.
2. 한 번에 맨 위 원판 하나만 옮깁니다.
3. 어느 순간에도 큰 원판을 작은 원판 위에 놓지 않습니다.
4. 보조 기둥을 포함해 기둥은 세 개입니다.

마지막 조건이 중요합니다. 2ⁿ−1 공식은 기둥이 세 개인 고전 문제에 대한 결과입니다. 기둥이 네 개 이상이면 더 짧은 경로가 가능하며 같은 점화식을 그대로 적용할 수 없습니다. 또한 한 번에 여러 원판을 옮기거나 큰 원판을 작은 원판 위에 놓을 수 있게 바꾸면 다른 문제가 됩니다.

작은 원판 수로 직접 확인해 보기

원판이 하나면 한 번이면 충분합니다. 원판이 두 개면 작은 원판을 보조 기둥으로 옮기고, 큰 원판을 목적 기둥으로 옮긴 다음, 작은 원판을 큰 원판 위에 올립니다. 세 번보다 줄일 수 없습니다. 큰 원판을 움직이기 전과 후에 작은 원판이 반드시 이동해야 하기 때문입니다.

점화식 T(n)=2T(n−1)+1은 어떻게 나오나

T(n)을 원판 n개를 규칙대로 옮기는 데 필요한 최소 이동 횟수라고 하겠습니다. 가장 큰 원판은 처음에는 출발 기둥 맨 아래에 있습니다. 이 원판을 꺼내려면 위에 있는 n−1개를 보조 기둥으로 모두 옮겨야 합니다. 이 하위 문제는 원판 n−1개의 하노이 문제이므로 최소 T(n−1)번이 필요합니다.

이제 가장 큰 원판을 출발 기둥에서 목적 기둥으로 한 번 옮깁니다. 마지막으로 보조 기둥에 쌓인 n−1개를 목적 기둥의 가장 큰 원판 위로 옮겨야 합니다. 크기 관계와 규칙이 처음과 같으므로 다시 최소 T(n−1)번이 필요합니다.

T(n) = T(n−1) + 1 + T(n−1) = 2T(n−1)+1

초깃값은 T(0)=0 또는 T(1)=1로 둘 수 있습니다. 두 표현은 같은 해를 줍니다. 여기서 ‘최소’라는 말을 얻으려면 이 절차가 가능하다는 사실만으로는 부족합니다. 어떤 해법도 이보다 적게 움직일 수 없다는 하한까지 보여야 합니다.

왜 이보다 적게 옮길 수 없는가: 최소성 증명

가장 큰 원판 n을 목적 기둥으로 옮기는 순간을 보겠습니다. 그 원판 위에는 아무것도 없어야 하므로 작은 원판 n−1개는 모두 출발 기둥을 떠나 보조 기둥에 쌓여 있어야 합니다. 목적 기둥도 비어 있어야 가장 큰 원판을 그곳에 놓을 수 있습니다. 따라서 큰 원판을 옮기기 전에는 n−1개짜리 문제를 적어도 T(n−1)번 수행해야 합니다.

가장 큰 원판을 한 번 옮긴 다음에도 n−1개는 보조 기둥에 남아 있습니다. 목표 상태를 만들려면 이 묶음을 가장 큰 원판 위로 다시 옮겨야 하므로 적어도 T(n−1)번이 더 필요합니다. 결국 어떤 합법적인 해법도 2T(n−1)+1번보다 짧을 수 없습니다. 앞에서 그 횟수로 실제 이동하는 절차를 제시했으므로 상한과 하한이 일치합니다.

점화식을 전개해 닫힌식 구하기

점화식을 반복해서 대입하면 패턴이 선명해집니다. T(n)=2T(n−1)+1이고 T(n−1)=2T(n−2)+1이므로 T(n)=2²T(n−2)+2+1입니다. 다시 펼치면 T(n)=2³T(n−3)+2²+2+1이 됩니다.

T(n)=2ⁿT(0)+(1+2+2²+···+2ⁿ⁻¹)

T(0)=0이고 괄호 안은 공비가 2인 등비수열의 합입니다. 1+2+···+2ⁿ⁻¹=(2ⁿ−1)/(2−1)=2ⁿ−1이므로 T(n)=2ⁿ−1입니다. 수학적 귀납법으로도 확인할 수 있습니다. n=0에서 성립하고, T(k)=2ᵏ−1이라고 가정하면 T(k+1)=2(2ᵏ−1)+1=2ᵏ⁺¹−1입니다.

재귀 알고리즘은 어떤 순서로 움직이나

원판 n개를 A에서 C로 옮기고 B를 보조로 쓰는 절차는 세 문장으로 적을 수 있습니다. 먼저 n−1개를 A에서 B로 옮기고, 원판 n을 A에서 C로 옮긴 뒤, n−1개를 B에서 C로 옮깁니다. 두 개의 n−1 문제도 같은 규칙으로 더 작은 문제를 호출합니다.

1. n=0이면 아무 일도 하지 않고 끝냅니다.
2. n−1개를 출발 기둥에서 보조 기둥으로 옮깁니다.
3. 가장 큰 원판 하나를 출발 기둥에서 목적 기둥으로 옮깁니다.
4. n−1개를 보조 기둥에서 목적 기둥으로 옮깁니다.

실제 이동을 모두 출력하는 알고리즘의 시간은 이동 횟수와 같아 Θ(2ⁿ)입니다. 단순히 횟수만 구한다면 2ⁿ−1을 계산하면 되므로 모든 이동을 생성할 필요가 없습니다. 재귀 호출의 최대 깊이는 n이며, 호출 스택은 보통 O(n) 공간을 사용합니다.

원판 하나가 늘 때마다 일이 거의 두 배가 된다

64개 원판을 초당 한 번 옮길 때 약 5,845억 년이라는 값은 2⁶⁴−1초를 1년 약 31,556,952초로 나눈 근삿값입니다. 실제로 쉬지 않고 정확히 한 번씩 움직인다는 비현실적인 가정 아래에서도 그렇습니다. 원판 수가 한 개 늘면 T(n+1)=2T(n)+1이므로 이동 횟수는 거의 두 배가 됩니다.

이런 지수 증가는 두께가 매번 두 배가 되는 종이를 42번 접으면 달 거리보다 두꺼워지는 계산과 같은 구조를 가집니다. 시작값은 작아도 반복 횟수가 늘면 선형 증가와 전혀 다른 규모가 됩니다.

모든 최소 해법에서 가장 큰 원판은 한 번만 움직인다

최소 해법은 가장 큰 원판을 정확히 한 번 옮깁니다. 두 번 이상 옮기면 목표 기둥이 아닌 곳을 거쳐야 하고, 그때마다 작은 원판들을 치우고 다시 쌓는 추가 작업이 생깁니다. 가장 큰 원판을 출발지에서 목적지로 직접 한 번 옮기는 경로보다 짧아질 수 없습니다.

원판별 이동 횟수도 규칙적입니다. 가장 큰 원판은 1번, 그다음 원판은 2번, 그다음은 4번 움직입니다. 가장 작은 원판은 2ⁿ⁻¹번 움직입니다. 이를 모두 더하면 1+2+···+2ⁿ⁻¹=2ⁿ−1이 됩니다.

이진수와 그레이 코드로 보는 하노이의 탑

최소 해법의 각 단계는 이진수 변화와 연결됩니다. 이동 번호를 1부터 세었을 때 어떤 원판이 움직이는지는 그 수를 2로 몇 번 나눌 수 있는지와 관련됩니다. 홀수 번째 이동에서는 가장 작은 원판이 움직이고, 2로 한 번만 나누어지는 번호에서는 두 번째 원판이 움직이는 식입니다.

그레이 코드는 연속한 코드가 정확히 한 비트만 다른 이진 표현입니다. 하노이의 탑 상태를 적절히 부호화하면 한 번에 원판 하나만 움직인다는 규칙과 대응시킬 수 있습니다. 다만 일반 이진수 자체가 곧 원판 배치라는 뜻은 아니며, 원판 방향과 기둥 배치를 정하는 대응 규칙이 필요합니다.

네 기둥 문제에는 2ⁿ−1을 적용하면 안 된다

기둥이 네 개라면 일부 작은 원판을 여분 기둥에 임시로 두어 이동을 줄일 수 있습니다. 이 변형은 레브 퍼즐 또는 네 기둥 하노이 문제로 알려져 있으며, 보통 프레임–스튜어트 방식과 관련해 설명됩니다. 고전적인 세 기둥 증명에서는 n−1개를 하나의 보조 기둥에 모두 쌓아야 했지만 네 기둥에서는 선택지가 늘어납니다.

따라서 ‘원판 n개이면 언제나 2ⁿ−1번’이라는 문장은 틀립니다. 정확한 문장은 ‘세 기둥, 한 번에 한 원판, 큰 원판을 작은 원판 위에 놓지 않는 고전 규칙에서 최소 횟수는 2ⁿ−1’입니다. 수학 공식은 전제를 함께 적어야 다른 변형에 잘못 적용되지 않습니다.

하노이의 탑에서 자주 생기는 오해

• 점화식으로 만든 절차가 가능하다는 사실만 말하고 최소성의 하한을 증명하지 않습니다.
• 기둥이 네 개 이상인 변형에도 2ⁿ−1을 그대로 사용합니다.
• T(1)=1을 쓰면서 전개 과정에서는 T(0)=0을 설명 없이 섞습니다.
• 2ⁿ−1과 2ⁿ을 같다고 적습니다. 점근적으로는 같은 Θ(2ⁿ)이지만 정확한 이동 횟수는 다릅니다.
• 모든 이동을 출력하는 시간복잡도와 횟수 값만 계산하는 연산 비용을 구분하지 않습니다.

하노이의 탑 점화식 FAQ

왜 T(n−1)이 두 번 필요한가요?

가장 큰 원판을 움직이기 전에 위의 n−1개를 치워야 하고, 움직인 뒤에는 그 n−1개를 다시 가장 큰 원판 위로 옮겨야 하기 때문입니다. 두 작업 모두 같은 크기의 하위 문제입니다.

2ⁿ−1은 정확한 값인가요, 근삿값인가요?

고전적인 세 기둥 규칙에서는 정확한 최소 횟수입니다. 시간복잡도를 말할 때는 상수와 낮은 차수 항을 생략해 Θ(2ⁿ)이라고 씁니다.

원판 64개를 정말 옮기면 5,845억 년이 걸리나요?

초당 정확히 한 번씩 쉬지 않고 움직인다는 가정에서 2⁶⁴−1초를 환산한 근삿값입니다. 물리적인 원판 이동 조건을 반영한 예측이 아니라 지수 증가의 규모를 보여 주는 계산입니다.

핵심 정리

세 기둥 하노이의 탑에서 가장 큰 원판을 옮기려면 작은 원판 n−1개를 먼저 치우고, 큰 원판을 한 번 옮긴 뒤, 작은 원판들을 다시 쌓아야 합니다. 그래서 T(n)=2T(n−1)+1이 강제됩니다. 이 절차는 실제 해법을 제공하고, 가장 큰 원판 전후에 각각 T(n−1)번이 반드시 필요하다는 논증은 더 짧은 해법이 없음을 보입니다.

점화식을 전개하거나 귀납법을 적용하면 T(n)=2ⁿ−1입니다. 원판 한 개가 늘 때 이동 횟수는 거의 두 배가 되며, 정확한 이동을 출력하는 알고리즘은 Θ(2ⁿ) 시간이 걸립니다. 이 결론은 고전적인 세 기둥 문제에 한정됩니다.

참고 자료

• MIT Mathematics for Computer Science, Recurrences and Towers of Hanoi
• Encyclopaedia Britannica, Tower of Hanoi
• NIST Dictionary of Algorithms and Data Structures, recursion