재귀 알고리즘 - 하노이 탑 이해와 효율적인 구현 방법

하노이 탑이란?

이 문제는 세 개의 기둥과 한 기둥에 쌓여 있는 원반들로 구성되어 있습니다. 원반의 크기는 모두 다르며, 규칙에 따라 큰 원반이 작은 원반 위에 있어서는 안 됩니다. 목표는 최소 이동 횟수로 한 기둥에 쌓여 있는 원반들을 다른 기둥으로 모두 옮기는 것입니다.

 

하노이 탑 규칙

1. 한 번에 한 개의 원반만 이동할 수 있습니다.
2. 원반은 세 개의 기둥 중 하나에만 있을 수 있습니다.
3. 큰 원반이 작은 원반 위에 있어서는 안 됩니다.
4. 모든 원반을 다른 기둥으로 모두 옮기면 끝입니다.

하노이 탑 문제 해결 방법

1. n-1개의 원반을 시작 기둥에서 보조 기둥으로 옮깁니다.
2. 남은 한 개의 원반을 시작 기둥에서 목표 기둥으로 옮깁니다.(+1)
3. 보조 기둥에 있는 n-1개의 원반을 목표 기둥으로 옮깁니다.
4. 이 때의 이동횟수를 더하면 2P(n-1) + 1이라는 점화식이 나옵니다.

하노이 탑 문제 해결 예시

원반이 3개 있을 경우

1. P(1) = 1
2. P(2) = 2P(1) + 1 = 3
3. P(3) = 2P(2) + 1 = 7

등비수열의 합 공식을 이용하면

P(n) = 1 + 2 + 2^2 + 2^3 ... + 2^n-1 = 2^n - 1 / 2 - 1 = 2^n - 1

 

하노이 탑 알고리즘 코드

function towerOfHanoi(n, start, to, sub) {
 if(n === 1) return;
 towerOfHanoi(n - 1, from, sub, to)
 towerOfHanoi(n - 1, sub, to, from)
}

 

n개의 원반을 이동한다고 했을 때 n-1개의 원반을 일단 도착지를 이용하여 보조로 이동하고 n번째 원반을 도착지로 이동하고 n -1 개의 원반을 다시 보조에서 출발지를 이용하여 도착지로 이동하면됩니다.