하노이의 탑은 대표적인 알고리즘 고전 문제 중 하나이다.
“3 개의 탑에 n 개의 원반이 꽂혀 있다. 1 번 탑에서 3 번탑으로 모든 원반을 이동시키려고 한다. 원반을 이동시킬 때는 가장 위에 있는 원반을 한번에 한개씩 이동시킬 수 있으며, 원반 위에 더 큰 원반이 오면 안된다.”
문제를 단순화해서 n = 1 개인 경우부터 생각해 보자.
이 경우, 원반을 1 번 탑에서 3 번 탑으로 이동시키면 된다. (1 번)
n = 2 인 경우,
우선 1 개의 원반을 2 번탑으로 보낸 후, (1 번)
나머지 1 개의 원반을 3 번탑으로 보낸 다음, (1 번)
다시 2 번탑의 원반을 3 번탑으로 보내면 된다 (1 번) (총 3 번)
n = 3 의 경우,
이 경우는 먼저 1 번탑에 있는 위에 2 개의 원반을 2 번탑으로 보낸 다음, (3 번)
나머지 1 개의 원반을 3 번탑으로 보내고, (1 번)
다시 2 번탑에 있는 2 개의 원반을 3 번탑으로 보내면 된다. (3 번) (총 7 번)
…
여기서 반복되는 부분이 보이는가?
n 개의 원반을 1 번 탑에서 3 번 탑으로 옮길 경우,
우선 1 번 탑에서 n-1 개의 원반을 2 번탑으로 옮기고,
나머지 1 개의 원반을 3 번탑으로 옮기고,
다시 n-1 개의 원반을 3 번탑으로 옮기면 된다.
이것을 알고리즘으로 구현하면 다음과 같다.
func getHanoi(n) {
if(n == 1) {
return 1;
} else {
return 1 + getHanoi(n-1) * 2;
}
}
getHanoi(3); // 3 개의 원반을 옮기려면 총 7 번 이동해야 한다.
재귀 호출은 잘만 사용하면 복잡한 문제도 사람이 이해하기 쉽게 알고리즘을 짤 수 있게 해준다.
하지만 많은 경우 n 이 커짐에 따라 복잡도가 급격히 증가하기 때문에(피보나치 수열 등) 최선의 방법인지 한번 더 생각해보아야 한다.