하노이의 탑 (원반 개수 8개)

최소 이동 횟수255회

2026년 5월 8일출제 횟수: 0정답률: 0%

❓ 퀴즈

프랑스의 수학자 에두아르 뤼카(Édouard Lucas)가 1883년에 발표한 퍼즐. 세 개의 기둥과 크기가 서로 다른 원반들이 주어졌을 때, 모든 원반을 정해진 규칙에 따라 다른 기둥으로 옮기는 것이 목표이다. 수학적 귀납법과 재귀 알고리즘을 설명할 때 반드시 등장하는 존재다. 다음의 세 가지 조건을 반드시 지켜야 한다. - 한 번에 하나의 원반만 옮길 수 있다. - 큰 원반이 작은 원반 위에 올라갈 수 없다. - 기둥 이외의 장소(바닥 등)에 원반을 내려놓을 수 없다.

수학적 원리 (원반 n개 기준) - 최소 이동 횟수 공식: 2^n - 1 - 원반 n개를 옮기기 위한 재귀적 단계: 1) 위의 n-1개 원반을 보조 기둥으로 이동 (2^(n-1) - 1번) 2) 가장 큰 원반을 목적지 기둥으로 이동 (1번) 3) 다시 보조 기둥의 n-1개 원반을 목적지 기둥으로 이동 (2^(n-1) - 1번) 결과: (2^(n-1) - 1) + 1 + (2^(n-1) - 1) = 2^n - 1 - 원반 8개의 경우 : 2^8 - 1 = 255회