하노이의 탑

하노이의 탑

하노이의 탑 이라는 문제는 일렬로 서있는 세 막대기 중 왼쪽 끝 막대기에 모든 원반들이 크기 순으로 꽂혀있고, 일정한 룰에 따라 그것을 전부 오른 쪽 끝 막대기로 이동하는 것을 묻는 문제이다. 아래는 하노이의 탑 사진 (wikipedia)

큰 원반이 항상 아래에 있어야 한다는 규칙을 준수하면서, 첫 번째 막대기에서 세 번째 막대기로 가는데에 가장 최단 수행 횟수가 존재할 거라 생각하는가? 만약 최단 수행이 존재한다면, 몇 번의 수행 만에 작업을 완료 할 수 있는가? 이에 대해 생각을 해볼 것이다.

하노이의 탑은 브라마의 탑이라고도 불리며 원래는 64개의 원반을 가지고 이동시키는 놀이로 부터 기원한다.

생각 step 1

처음부터 많은 수의 원반을 생각하지 말고 원반의 수를 줄여보자. 원반이 한 개일 땐, 수행 횟수 T = 1 이다. 원반이 두개 일 땐, 가장 작은 녀석을 두번째 막대기로 옮기고... 그리고 가장 큰 원반을 세번째로 옮기고 그 뒤 두번째 막대기에서 작은 원반을 꺼내어 세번째 막대기로 넣는다. 따라서 작업횟수 T=3 이다.

생각 step 2

원반이 세개일 때를 생각해보면, 다음 상황을 반드시 마주칠 것 이다. 나머지 두 원반이 두번째 막대기에 모두 꽂혀있고, 가장 큰 원반이 첫번째 막대기에서 세번째 막대기로 막 옮겨진 상황을 말이다. 아무리 원반이 많더라도 반드시 그 상황을 마주하게 된다.(1) 그렇다면 그 상황은 똑같은 문제로의 회귀인데, "두 번째 막대기에서 세 번째 막대기로의 원반 이동"이 된다. 머릿 속에 (1)과 같은 상황을 그려보자. 그리고 두번째 막대기와 첫번째 막대기의 자리를 바꿔보면 "첫 번째 막대기에서 세 번째 막대기로 2개의 원반을 옮기기"가 된다. 첫번째 막대기와 두번째 막대기는 수행하는 역할에 있어 차이가 없음을 알 수 있다.

생각 step 3, 증명

위 상황을 수식으로 정리해보자. T_3 = T_2 + 1 + T_2가 된다. 앞선 T_2는 2개의 원반을 2번째 막대기로 옮기는 작업을 뜻하며 뒤의 T_2는 2번째 막대기에서 3번째 막대기로 옮기는 작업을 뜻한다. 그리고 남은 1은 가장 큰 원반을 세번째 막대기로 옮긴 작업이다.

이를 일반화 하면 다음과 같다.

T_n = 2 * T_(n-1) + 1

여러분은 아마도 위의 생각 진행이 최소의 진행이라고 생각하지 않을 수 있다. 따라서, 생각 step에 따른 진행이 단지 그것만으로 충분한 횟수라고 생각하여 다음과 같은 =을 <=으로 바꾸고 싶을것이다.

T_n <= 2 * T_(n-1) + 1

하지만 생각 step보다 더 적은 이동 횟수를 제안할 수 있을까? 가장 큰 원반이 움직이기 위해선 나머지 n-1 개의 원반이 반드시 움직여야한다. 그러면 T_(n-1)회의 이동이 필요하다. 그리고 큰 원반을 반드시 한번 옮기고, 다시 나머지 원반을 T_(n-1)회 이동 시킨다. 그렇다면 다음이 성립가능하다.

T_n >= 2 * T_(n-1) + 1

따라서, 다음과 같다. (2)

T_n = 2 * T_(n-1) + 1
T_0 = 0

점화식

점화식의 해를 구해보자. 점화식의 해를 구하는 것은 쉽지 않다. 그러나 위 식 (2) 에 양변에 각각 1을 더하면 해를 구하기 쉬워진다.

T_n + 1 = 2 * T_(n-1) + 2
T_0 + 1 = 1

Let, T_n + 1 = S_n

S_n = 2 * S_(n-1)
S_0 = 1

따라서, S_n = 2^n, T_n = 2^n - 1 이다.