하노이의 탑

기둥 A에 쌓인 원반을 규칙에 맞게 다른 기둥으로 모두 옮기는 하노이의 탑 퍼즐입니다. 직접 풀어 보거나, 재귀를 배우는 수업에서 자동 풀이와 풀이 순서 목록을 함께 볼 수 있습니다.

사용 방법

1. '원반 수'를 3~10개 가운데에서 고릅니다.
2. 맨 위 원반을 다른 기둥으로 끌어 놓거나, 기둥을 눌러 원반을 들고 다른 기둥을 눌러 내려놓습니다. 숫자 키 1, 2, 3도 됩니다.
3. 잘못 옮겼으면 '되돌리기'를, 처음부터 하려면 '처음부터'를 누릅니다.
4. 막히면 '자동 풀이 보기'로 지금 상태부터의 풀이를 봅니다. '속도'를 바꾸거나 '일시정지'한 뒤 '한 단계'씩 넘길 수 있습니다.

계산 방식과 참고

• 규칙은 한 번에 원반 하나만, 기둥의 맨 위 원반만 옮기며, 작은 원반 위에 큰 원반을 놓을 수 없다는 것입니다.
• 원반 n개의 최소 이동 수는 2ⁿ − 1입니다. n − 1개를 옆으로 옮기고, 가장 큰 원반을 한 번 옮긴 뒤, n − 1개를 다시 그 위로 옮겨야 하기 때문입니다.
• 원반 수별 최고 기록은 이 브라우저에 저장됩니다. 자동 풀이를 쓴 게임은 기록하지 않습니다.

자주 묻는 질문

하노이의 탑 최소 이동 횟수는 몇 번인가요?

원반 n개일 때 2ⁿ − 1번입니다. 3개는 7번, 4개는 15번, 5개는 31번, 10개는 1,023번입니다.

하노이의 탑을 푸는 요령이 있나요?

홀수 번째 이동에서는 가장 작은 원반을 늘 같은 방향으로 한 기둥씩 옮깁니다. 짝수 번째 이동에서는 가장 작은 원반을 쓰지 않는, 둘 수 있는 유일한 수를 둡니다.

하노이의 탑이 재귀 알고리즘의 예제로 쓰이는 이유는 무엇인가요?

원반 n개의 풀이가 원반 n − 1개의 풀이 두 번과 가장 큰 원반 한 번의 이동으로 이루어지기 때문입니다. 그래서 T(n) = 2·T(n − 1) + 1입니다.

풀이 순서를 한꺼번에 볼 수 있나요?

'풀이 순서 목록'을 펼치면 모든 이동이 '원반 1: A → C' 같은 형식으로 나옵니다.