하노이탑 알고리즘

30층짜리 하노이탑을 옮기려면 무려 34년간을 쉬지도 않고 옮겨야 한다.

하노이탑을 옮기려면 원반을 모두 (2의 n승)-1번만큼 옮겨야 한다. 원반이 3개라면 총 7번을 옮겨야 한다. 마찬가지로 n이 커지면 -1은 큰 의미가 없으므로 하노이탑 알고리즘의 계산 복잡도는 O(2n)으로 표현할 수 있다. 이는 2를 n번 제곱한 값이므로 n이 커짐에 따라 값이 기하급수적으로 증가한다. 그래서 원반 하나를 옮기는 데 1초가 걸린다고 가정하더라도 30층짜리 하노이 탑을 옮기려면 무려 34년간 먹지도 쉬지도 않고 원반만 옮겨야 한다(이승찬, 2017).

재귀 호출을 이용한 하노이탑 알고리즘 함수의 작성은 간단하나, 직접 순서를 짜는 것은 일련의 과정을 머릿속에서 그릴 수 없다면 시도조차 하기 어려울 것이다. 그래서 머릿속에서 먼저 처음 그림의 과정을 하나씩 그려보고 수식으로 표현할 줄 아는 단계를 거쳐야 원반 세 개를 옮기는 것의 일반적인 경우(원반이 n개일 때)도 생각할 수 있다.

알고리즘을 적어보면 아래와 같다.

1. 원반이 한 개면 그냥 옮기면 끝이다(종료 조건).
2. 원반이 n개일 때
  1) 1번 기둥에 있는 n개 원반 중 n-1개를 2번 기둥으로 옮긴다(3번 기둥을 보조 기둥으로 사용).
  2) 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮긴다.
  3) 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮긴다(1번 기둥을 보조 기둥으로 사용).

원반이 한 개일 때가 '종료 조건'에 해당한다. 원반 n개 문제를 풀려면 n-1개 원반 문제를 풀어야 하는데, 이는 바로 '좀 더 작은 값으로 자기 자신을 호출하는 과정'이다. 따라서 이 문제는 전형적인 재귀 호출 알고리즘에 해당한다(이승찬, 2017).

같은 과정의 반복이 이루어지는 하노이탑 옮기기의 재귀(Recusion)

참조

1) 이승찬 저. (2017). 모두의 알고리즘 with 파이썬, 서울:(주)도서출판 길벗.

2) Towers Of Hanoi. (2018, May 28). Retrieved from https://algorithms.tutorialhorizon.com/towers-of-hanoi/