하노이의 탑

 

n+1개의 탑을 이동하려 할 때, 가장 큰 원반을 무시하고, n개를 b로 이동 시킨다. 가장 큰 원반을 c로 이동시킨 뒤 이동시키면 된다. 처음에  b로 n개의 탑을 이동시킬 때, c와 나누어서 이동시켜야 하기 때문에 계산적으로 해야한다.

 

n개 탑 문제는 n-1 탑 문제를 활용하면 되고, n-1은 n-2를 활용하면 되기 때문에 재귀적 알고리즘이다.

 

계산 시간

n-1개를 A에서 B로 이동시킬 때, n-1

가장 큰 원반을 C로 이동시킬 때, 1

B에 있는 n-1개를 C로 이동시킬 때, n-1이 필요하므로

T(n) = 2T(n-1) + 1 = 2^n - 1