inthink.guide
상점홈으로 돌아가기

플레이하고, 예측하고, 이해하세요.

하노이의 탑

원반 3~5개로 플레이하고 현재 배치에 맞는 힌트를 받아 보세요. 짧은 애니메이션 두 개로 재귀 전략을 배우고 언제든 단계별 풀이를 열 수 있습니다.

하노이의 탑 플레이
ABC원반 44원반 33원반 22원반 11

작은 원반 더미를 옮겨 가장 큰 원반의 길을 열어 주세요.

하노이의 탑 규칙

  1. 모든 원반을 기둥 A에서 기둥 C로 옮깁니다.
  2. 한 번에 하나만, 기둥 맨 위의 원반을 옮깁니다.
  3. 큰 원반을 작은 원반 위에 올릴 수 없습니다.

하노이의 탑 플레이

출발 기둥을 고른 뒤 도착 기둥을 고르세요. 숫자는 크기를 나타내며 1이 가장 작습니다. 한 수를 되돌리거나 처음부터 다른 방법을 시도할 수 있습니다.

0회 이동
ABC원반 33원반 22원반 11

출발 기둥을 고른 뒤 도착 기둥을 고르세요.

힌트는 현재 배치에서 시작하며 원반을 대신 움직이지 않습니다. 규칙을 지킨 우회도 해결할 수 있습니다.

하노이의 탑 푸는 방법

가장 큰 원반부터 생각하세요. 원반 네 개의 예에서는 작은 원반 세 개가 막고 있습니다. 원반 4를 옮기기 전에 더 작은 문제를 풉니다.

  1. 작은 더미를 옆으로 옮기기

    C를 보조 기둥으로 써서 원반 1, 2, 3을 A에서 B로 옮깁니다. 원반 4는 A에 둡니다. 이제 C가 비고 원반 4가 드러납니다.

    ABC원반 44원반 33원반 22원반 11

  2. 가장 큰 원반 옮기기

    원반 4를 A에서 C로 옮깁니다. 이 한 수로 가장 큰 원반이 최종 위치에 도착합니다.

    ABC원반 44원반 33원반 22원반 11

  3. 작은 더미를 목적지로 옮기기

    A를 보조로 써서 원반 1, 2, 3을 B에서 C로 옮깁니다. 원반 4 위에 올리면 퍼즐이 완성됩니다.

    ABC원반 44원반 33원반 22원반 11

작은 더미도 같은 세 단계 계획을 씁니다. 가장 큰 원반 위를 비우고, 큰 원반을 옮기고, 작은 더미를 그 위로 옮깁니다. 원반이 하나면 바로 옮깁니다. 이것이 재귀입니다. 부분 문제마다 출발, 도착, 보조 기둥의 역할이 바뀝니다.

다음 목표를 예측하며 배우기

독립적인 네 원반 예제라서 플레이 중인 배치는 변하지 않습니다. 멈추거나 한 수씩 보고, 예측에 답하거나 설명을 열어 보세요.

1. 가장 큰 원반의 길 열기

작은 원반 세 개가 원반 4의 길을 여는 모습을 봅니다. 큰 원반을 옮기기 전 어디에 있어야 할지 예측하세요.

독립적인 네 원반 예제

목표: C을 보조로 써서 원반 3개를 A에서 B로 옮기기.

ABC원반 44원반 33원반 22원반 11

먼저 길을 엽니다. 맨 위 세 원반을 A에서 B로 옮기세요.

8회 중 0회

2. 작은 문제 반복하기

원반 4는 이미 C에 있습니다. 남은 것은 기둥 역할만 달라진 세 원반 문제입니다.

독립적인 네 원반 예제

목표: A을 보조로 써서 원반 3개를 B에서 C로 옮기기.

ABC원반 44원반 33원반 22원반 11

원반 4는 C에 둡니다. 이제 세 원반을 B에서 C로 옮깁니다.

A를 보조로 세 원반을 B에서 C로 옮길 때 원반 1은 먼저 어디로 갈까요?

7회 중 0회

단계별 풀이

모든 원반이 A에 있는 상태에서 시작해 C에서 끝납니다. 예제를 바로 열어도 플레이 중인 배치는 유지됩니다.

최소 이동 횟수

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

표준 풀이는 작은 더미를 두 번, 가장 큰 원반을 한 번 옮기므로 T(n) = 2T(n − 1) + 1입니다. 원반 하나는 한 수가 필요하므로 n개의 최소 횟수는 2ⁿ − 1입니다.

원반 3개: 7회. 4개: 15회. 5개: 31회.

원반 3개 — 7회

시작: 모든 원반은 A. 도착: C. 원반 1이 가장 작습니다.

  1. 원반 1을 A에서 C로 옮깁니다.
  2. 원반 2을 A에서 B로 옮깁니다.
  3. 원반 1을 C에서 B로 옮깁니다.
  4. 원반 3을 A에서 C로 옮깁니다.
  5. 원반 1을 B에서 A로 옮깁니다.
  6. 원반 2을 B에서 C로 옮깁니다.
  7. 원반 1을 A에서 C로 옮깁니다.
원반 4개 — 15회

시작: 모든 원반은 A. 도착: C. 원반 1이 가장 작습니다.

  1. 원반 1을 A에서 B로 옮깁니다.
  2. 원반 2을 A에서 C로 옮깁니다.
  3. 원반 1을 B에서 C로 옮깁니다.
  4. 원반 3을 A에서 B로 옮깁니다.
  5. 원반 1을 C에서 A로 옮깁니다.
  6. 원반 2을 C에서 B로 옮깁니다.
  7. 원반 1을 A에서 B로 옮깁니다.
  8. 원반 4을 A에서 C로 옮깁니다.
  9. 원반 1을 B에서 C로 옮깁니다.
  10. 원반 2을 B에서 A로 옮깁니다.
  11. 원반 1을 C에서 A로 옮깁니다.
  12. 원반 3을 B에서 C로 옮깁니다.
  13. 원반 1을 A에서 B로 옮깁니다.
  14. 원반 2을 A에서 C로 옮깁니다.
  15. 원반 1을 B에서 C로 옮깁니다.
원반 5개 — 31회

시작: 모든 원반은 A. 도착: C. 원반 1이 가장 작습니다.

  1. 원반 1을 A에서 C로 옮깁니다.
  2. 원반 2을 A에서 B로 옮깁니다.
  3. 원반 1을 C에서 B로 옮깁니다.
  4. 원반 3을 A에서 C로 옮깁니다.
  5. 원반 1을 B에서 A로 옮깁니다.
  6. 원반 2을 B에서 C로 옮깁니다.
  7. 원반 1을 A에서 C로 옮깁니다.
  8. 원반 4을 A에서 B로 옮깁니다.
  9. 원반 1을 C에서 B로 옮깁니다.
  10. 원반 2을 C에서 A로 옮깁니다.
  11. 원반 1을 B에서 A로 옮깁니다.
  12. 원반 3을 C에서 B로 옮깁니다.
  13. 원반 1을 A에서 C로 옮깁니다.
  14. 원반 2을 A에서 B로 옮깁니다.
  15. 원반 1을 C에서 B로 옮깁니다.
  16. 원반 5을 A에서 C로 옮깁니다.
  17. 원반 1을 B에서 A로 옮깁니다.
  18. 원반 2을 B에서 C로 옮깁니다.
  19. 원반 1을 A에서 C로 옮깁니다.
  20. 원반 3을 B에서 A로 옮깁니다.
  21. 원반 1을 C에서 B로 옮깁니다.
  22. 원반 2을 C에서 A로 옮깁니다.
  23. 원반 1을 B에서 A로 옮깁니다.
  24. 원반 4을 B에서 C로 옮깁니다.
  25. 원반 1을 A에서 C로 옮깁니다.
  26. 원반 2을 A에서 B로 옮깁니다.
  27. 원반 1을 C에서 B로 옮깁니다.
  28. 원반 3을 A에서 C로 옮깁니다.
  29. 원반 1을 B에서 A로 옮깁니다.
  30. 원반 2을 B에서 C로 옮깁니다.
  31. 원반 1을 A에서 C로 옮깁니다.

내 배치가 예제와 다르면?

크기 규칙을 지킨 모든 배치는 C에 도달할 수 있습니다. 이전 배치로 돌아가는 것은 반복이지 막다른 길이 아닙니다. 위 공식은 표준 시작에만 적용되며 임의 배치의 남은 횟수가 아닙니다. 현재 배치에 맞는 힌트를 사용하세요.

퍼즐 →