알고리즘 - 하노이의 탑 재귀적 접근 (Hanoi Tower and Recursive Solving)

하노이의 탑의 규칙은 아래 포스트를 참고한다.

 

https://m.blog.naver.com/jaeyoon_95/221762231876

[프로그래머스] 하노이의 탑

 

하노이의 탑은 보통 재귀 함수를 사용하여 풀곤 한다. 하노이의 탑을 왜 재귀 함수로 풀 수 있는지, 수학적 접근으로 알아보자. 아래의 하노이의 탑은 하노이의 탑 문제에 대한 풀이를 뜻한다.

 

먼저 원판이 n개 있다고 했을 때, 한 원판에서 다른 원판까지 옮기는 데 필요한 최소 움직임은 m = 2^n - 1이다.

 

하노이의 탑의 정답은 언제나 존재한다는 것과, 최소 움직임이 위와 같다는 것을 수학적 귀납법으로 증명해보자.

 

먼저 위 공식이 양의 정수 n에 대해 (n >= 1) 언제나 적용된다고 가정하자.

 

먼저 base case인 n = 1일 때, 한 원판을 다른 한 원판으로 옮기는 데 필요한 움직임은 당연히 한 번이며, 아래 식은 참이므로 base case가 증명되었다.

 

 

이제 P(n) 이 성립한다고 가정한다. P(n)이 항상 성립할 때, P(n+1)이 성립함을 보여야 한다. P(n+1)의 케이스는 다음 그림과 같다.

 

 

n+1 번째 원반은 일단 무시하고, n개의 원반을 먼저 2번으로 옮긴다 가정하자. 이 때, P(n)이 성립한다 가정하였으므로 필요한 움직임 수는 아래와 같다.

 

 

그럼 원판들은 다음과 같이 되어있을 것이다.

 

 

이제 n+1 번째 원반을 3번으로 옮긴다.

 

 

이제 다시 n+1 번째 원반을 무시한 채로 n개의 원반을 3번으로 옮겨준다. 이 때 필요한 움직임 수는 마찬가지로 2^n - 1 이다.

 

 

위와 같은 방법을 사용하면 하노이의 탑은 언제나 정답이 존재한다는 것을 알 수 있다. 이제 n+1 개의 원판을 옮기는 데든 움직임의 수를 세어보면,

 

 

이며, 중간의 1은 n+1 번째 원판을 1번에서 3번으로 옮긴 움직임이다. P(n)은 2^n - 1 이므로,

 

 

base case가 P(n)을 따르므로, P(n) = 2^n - 1 임이 증명되었다. 그렇다면 이를 재귀함수로 푼다는 것은 어떤 것을 의미할까?

 

하노이의 탑 움직임을 원판 n개에 따라 실행하는 함수 f가 있다고 했을 때, 위 풀이법을 참고하여 풀어보면 n+1 개의 원판이 있을 때에는 f(n)을 두 번 호출해야 한다. 그리고 각 f(n)은 다시 f(n-1)을 두 번 호출할 것이고, 이와 같이 재귀적으로 하노이의 탑 해법을 재귀 함수로 얻어낼 수 있다.

 

 

출처

https://m.blog.naver.com/jaeyoon_95/221762231876