🗼하노이 탑 최소 이동 횟수 계산기

원반 개수를 입력하면 하노이 탑 최소 이동 횟수(2ⁿ−1)와 이동 시간 계산

원반 개수 (1~30)

개

1회 이동에 걸리는 시간

초

하노이 탑 최소 이동 횟수 계산기 사용법

하노이 탑은 세 개의 기둥과 크기가 서로 다른 원반 여러 개로 이루어진 퍼즐입니다. 규칙은 간단합니다. 한 번에 한 개의 원반만 옮길 수 있고, 큰 원반을 작은 원반 위에 올릴 수 없으며, 모든 원반을 다른 기둥으로 옮기면 완성입니다. 이 계산기는 원반 개수를 입력하면 규칙을 지키면서 옮길 수 있는 최소 이동 횟수와, 1회 이동에 걸리는 시간을 곱한 예상 총 소요 시간을 함께 계산해줍니다.

최소 이동 횟수는 항상 2ⁿ−1(n은 원반 개수)로 정해집니다. 원반이 하나 늘어날 때마다 이동 횟수는 정확히 두 배 넘게 늘어나는 지수적 증가를 보입니다. 예를 들어 원반 10개는 1,023회면 충분하지만, 원반 20개는 1,048,575회로 훌쩍 뛰어오릅니다. 이 급격한 증가 패턴 때문에 하노이 탑은 재귀 알고리즘과 지수함수를 설명할 때 대표적인 예시로 자주 사용됩니다.

흔히 알려진 '세상이 끝나는 하노이 탑' 전설에서는 원반 64개를 사제들이 옮기고 있으며, 다 옮기면 세상이 끝난다고 합니다. 1초에 한 번씩 쉬지 않고 옮겨도 약 5,800억 년이 걸리므로, 실제로는 걱정할 필요가 없는 셈입니다.

자주 묻는 질문

원반이 64개면 정말 얼마나 걸리나요?

원반 64개를 1초에 한 번씩 옮긴다고 가정하면 2⁶⁴−1회로 약 5,800억 년이 걸립니다. 우주의 나이보다 훨씬 길어서 '세상이 끝나기 전에는 불가능하다'는 전설이 생겼습니다.

최소 이동 횟수 공식은 왜 2ⁿ−1인가요?

원반 n개를 옮기려면 위 n−1개를 보조 기둥으로 옮기고(2ⁿ⁻¹−1회), 가장 큰 원반을 옮긴 뒤(1회), 다시 n−1개를 옮기는(2ⁿ⁻¹−1회) 과정이 필요해 총 2ⁿ−1회가 됩니다.

하노이 탑 최소 이동 횟수 계산기 사용법

자주 묻는 질문

함께 보면 좋은 도구