원판을 이동시켜 탑을 옮기는 클래식 퍼즐
왼쪽 기둥의 모든 원판을 오른쪽 기둥으로 옮기면 됩니다. 한 번에 하나의 원판만 옮길 수 있고, 큰 원판 위에 작은 원판만 올릴 수 있습니다. 원판을 클릭하면 선택되고, 기둥을 클릭하면 이동합니다.
원판이 n개일 때 최소 이동 횟수는 2^n - 1입니다. 3개는 7번, 4개는 15번, 5개는 31번, 6개는 63번, 7개는 127번이 필요합니다. 이보다 적은 횟수로는 수학적으로 불가능합니다.
재귀적 사고가 핵심입니다. n개의 원판을 옮기려면: (1) 위의 n-1개를 보조 기둥으로, (2) 가장 큰 원판을 목표 기둥으로, (3) n-1개를 목표 기둥으로 옮깁니다. 원판이 홀수 개면 첫 수는 가장 작은 원판을 오른쪽으로, 짝수 개면 가운데로 옮기세요.
1883년 프랑스 수학자 에두아르 뤼카가 발명했습니다. 전설에 따르면 인도 베나레스 사원의 승려들이 64개의 금 원판을 옮기고 있으며, 완료되면 세상이 끝난다고 합니다. 64개 원판의 최소 이동 횟수는 약 1844경 번으로, 1초에 1번씩 옮겨도 약 5,849억 년이 걸립니다.
하노이의 탑은 재귀(recursion) 알고리즘의 대표적인 예제로, 컴퓨터 과학 교육에서 널리 사용됩니다. 재귀적 사고방식, 분할 정복(divide and conquer) 전략, 시간 복잡도(O(2^n)) 개념을 직관적으로 이해할 수 있습니다.
하노이의 탑(Tower of Hanoi)은 1883년 프랑스 수학자 에두아르 뤼카가 발명한 클래식 수학 퍼즐입니다. 세 개의 기둥과 크기가 다른 원판으로 구성되며, 모든 원판을 규칙에 맞게 다른 기둥으로 옮기는 것이 목표입니다. 한 번에 하나의 원판만 옮길 수 있고, 큰 원판 위에 작은 원판만 올릴 수 있습니다. 3개부터 8개까지 원판 수를 선택할 수 있으며, 자동 풀이 기능과 되돌리기 기능을 제공합니다. 재귀 알고리즘의 대표적 예제로 컴퓨터 과학 교육에 널리 활용되며, 논리적 사고력과 문제 해결 능력을 키울 수 있습니다. 설치 없이 브라우저에서 바로 플레이할 수 있는 무료 온라인 퍼즐 게임입니다.