하노이의 탑 전략: 완벽한 풀이

1. 가장 작은 원판이 리듬을 정한다

두 번째 수마다 가장 작은 원판을 옮깁니다. 그 원판을 옮기는 두 수 사이에는 그 원판과 관계없는 둘 수 있는 수가 정확히 하나 있습니다. 그 수를 두세요.

2. 가장 작은 원판은 어느 쪽으로 가나?

가장 작은 원판은 세 기둥을 항상 같은 방향으로 돕니다.

• 원판 수가 홀수: 처음에 목표 기둥으로 옮기고, 왼쪽 → 오른쪽 → 가운데 → 왼쪽... 순으로 계속합니다.
• 원판 수가 짝수: 처음에 가운데 기둥으로 옮기고, 왼쪽 → 가운데 → 오른쪽 → 왼쪽... 순으로 계속합니다.

3. 재귀적으로 생각하기

원판 n개를 A에서 C로 옮기려면, 위의 n−1개를 B로 옮기고, 가장 큰 원판을 C로 옮긴 다음, B의 n−1개를 C로 옮깁니다. 각 단계는 더 작은 같은 퍼즐입니다.

4. 되돌리지 않기

원판을 방금 온 자리로 다시 옮긴다면 두 수를 낭비한 것입니다. 완벽한 풀이에서는 절대 그런 일이 없습니다.

최종 업데이트 2026-10-20