하노이의 탑

하노이의 탑(Tower of Hanoi)은 프랑스의 수학자 에두아르 뤼카(Édouard Lucas)가 1883년에 클라우스 교수(professeur N. Claus)라는 필명으로 발표한 수학 퍼즐이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들로 구성되며, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 세 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한 번에 한 개의 원판만 옮길 수 있다.
2. 가장 위에 있는 원판만 이동할 수 있다.
3. 큰 원판이 작은 원판 위에 있어서는 안 된다.

유래

하노이의 탑은 1883년 에두아르 뤼카가 발표하였다. 1년 후 앙리 드 파르빌(Henri de Parville)은 다음과 같은 이야기와 함께 하노이의 탑을 소개하였다. 인도 베나레스에 있는 한 사원에는 세 개의 다이아몬드 바늘이 동판 위에 세워져 있고, 그중 하나에 신이 64개의 순금 원판을 끼워 놓았다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 규칙에 따라 원판을 하나씩 옮기며, 이 일이 끝날 때 탑은 무너지고 세상은 종말을 맞이하게 된다는 내용이다. 이후 라우즈 볼, 가드너 등이 하노이의 탑을 소개하면서 널리 알려졌다.

수학적 성질

하노이의 탑 문제는 재귀 호출(recursion)을 이용하여 풀 수 있는 가장 유명한 예제 중 하나로, 프로그래밍 수업에서 알고리즘 예제로 많이 사용된다. 일반적으로 원판이 n개일 때, 최소 이동 횟수는 2ⁿ - 1번이다(2ⁿ - 1은 메르센 수라고 부른다). 예를 들어 원판이 3개인 경우 최소 7번(2³ - 1 = 7)의 이동이 필요하다.

한 번의 실수 없이 64개의 원판을 옮기는 데 필요한 이동 횟수는 2⁶⁴ - 1 = 18,446,744,073,709,551,615번(약 1.84 × 10¹⁹)이며, 1초당 한 번 원판을 움직일 경우 약 5,845억 년이 걸리는 것으로 계산된다. 이는 우주의 나이인 약 138억 년의 약 42.4배에 해당한다.

컴퓨터 과학에서의 의의

하노이의 탑은 재귀 알고리즘의 전형적인 예시로, 컴퓨터 과학 교육에서 널리 활용된다. 또한 문제 해결 능력, 논리 사고력 향상을 위한 교육 자료로도 사용되며, 다양한 프로그래밍 언어(파이썬, C++, 자바, 리스프 등)로 구현된 예제가 존재한다.