본 강좌는 스크립트 사용의 비중이 큽니다. 이 점 유의하면서 따라와주세요.
본 영상은 7층 짜리 하노이의 탑의 예시입니다. 이 강좌에서는 4층을 만듭니다.
강좌를 시작하기 전에, 하노이의 탑에 얽혀있는 전설에 대해 이야기를 해볼까요.
하노이의 탑은 불란서의 수학자인 에두아르 뤼카가 클라우스 교수라는 필명으로 1883년에 발표하였습니다. 1년 후 헨리 드 파르빌은 Claus가 Lucas의 애너그램임을 밝히면서 다음과 같은 이야기로 하노이의 탑을 소개하였습니다.
고대의 인도 베레나스에 있는 한 사원에는 세상의 중심을 상징하는 거대한 판이 있고, 그 위에는 다이아몬드로 만들어진 세 개의 기둥이 세워져 있다. 신이 세상을 창조할 때, 그 중 한 기둥에 크기가 모두 다른 64개의 황금 원반을 큰 것이 아래에, 그렇게 해서 점점 작은 원반을 위로 가게 해서 쌓았다. 그리고 이 64개의 원반을 ‘가장 위에 있는 원반만 한 번에 한 개만 옮길 수 있다’, ‘작은 원반 위에는 큰 원반이 올 수 없다’ 의 규칙을 지키며 모두 다른 기둥으로 옮겨야 한다. 이 64개의 원반을 모두 다른 기둥으로 옮겼을 때, 탑은 무너지고 세상의 종말이 온다고 한다.
얼핏 보면 그냥 옮기면 될 일이겠지만, 원반이 하나 증가할 때 마다 다른 기둥으로 옮기는 데 필요한 이동 횟수는 거의 2배로 증가합니다.
최소 이동 횟수(이론치)는 원반이 n개가 있을 때 $2^n-1$번 움직여야 하는데, 만약 3개가 있다면 최소 7번, 4개가 있다면 최소 15, 5개면 31, 6개면 63, …, 이런 식으로 증가하게 됩니다.
즉, 원반이 64개가 된다고 하면 최소 $2^{64}-1=18,446,744,073,709,551,615$번 움직여야 한다는 말인데, 이는 1초에 원반을 하나씩 움직인다고 해도 약 584,554,049,253년이 걸립니다. 이는 우주의 나이인 138억년의 42.4배에 달하죠. 출처
뭐 현실에서는 크레인으로 갖다가 64개 통째로 뽑아 들어 올리면 되니 상관은 없겠네요.
본 강좌에서는 본 강좌에서 제공하는 이미지로 만듭니다. 다음 구성품들을 모두 압축을 풀어 pictures 폴더 안에 저장해주세요.