2. 하노이의 탑 알고리즘

1. 코드

2. 결과

 

3. 해설

 하노이 타워 알고리즘은 규칙은 단 하나다. 큰 판이 작은 판보다 위로 쌓을 수 없다. 이 규칙을 준수하면서

출발지에서 목적지까지 탑을 크기에 맞게 고르게 쌓아야 한다.

 이 알고리즘은 컴퓨터공학 4년 내내 나에게 큰 어려움이었다. 왜냐하면 리커젼 기법에 대해서 아무것도

모를 때 배운 이 알고리즘은 그 당시의 내게 전혀 이해되지 않았고 그 때 느낀 막연한 두려움은 계속 내

마음을 잠식했기 때문이다. 그래서 이해하려는 노력을 해도 너무 어렵게만 느껴졌는데 하나의 아이디어를

만나고 이 알고리즘에 대해서 정확히 이해할 수 있었다.

 아이디어는 이렇다. 

 1. 맨 마지막 판을 제외한 나머지 판을 중간 경유지로 옮긴다.

 2. 맨 마지막 판을 목적지로 옮긴다.

 3. 중간 경유지에 있는 나머지 판들을 목적지로 옮긴다.

 뭔가 과정이 굉장히 생략되어 있는 느낌이다. 하지만 리커젼은 단순하게 따져보면 반복의 틀이다. 즉, 

위의 아이디어를 계속 반복한다. 전체 판이 3개라면 나머지 2개를 경유지로 옮기고 마지막 하나를 옮긴다.

그리고 다시 중간 경유지의 2개 판이 이 알고리즘의 시작이되어 그 때의 기준으로 다시 1개 판을 중간 

경유지로 옮기고 나머지 하나를 목적지로 옮긴다. 

 이 아이디어를 쉽게 이해할려면 출발지, 중간 경유지, 목적지가 하나의 리커젼을 돌 때마다 상대적으로

변한다는 것을 이해해야 한다. 고정된 틀인 파라미터와 그 안의 내용을 뜻하는 알규먼트의 차이와 같다.

 결론적으로 이 식을 간략화 하면 2개의 리커젼 함수에 길이가 하나씩 줄게되므로 감산 정복 마스터정리다.

 F(n) = 2F(n-1) + C

 이를 마스터 정리에 대입하면 n*2^(n/1) 이므로 최종적으로 O(2^n)이 된다.