스택 : 하노이 타워

 

■ Tower of Hanoi :: Algorithm of Stack

■ Count of Step ::  2n-1

■ Asymptotic Complexity :: O(2^n)

■ Composite :: 1. Source 2. Auxilary 3. Destination

 

■ Method :: 1. pop 2. push

 

하노이타워는 스택알고리즘을 설명할 때 자주 사용된다.

알고리즘의 조건은 다음과 같다.

1. A , B , C 세 기둥에서 N개의 원판이 있다.

2. A 기둥에 크기순으로 쌓여있는 원판을 C 기둥에 쌓아야 한다.

3. 원판은 크기순으로만 쌓을 수 있다. ( 더 큰 원판을 위에 두지 못한다. )

 

위 조건을 해석하면 다음 논리를 이해할 수 있다.

1. ( 스택구조 ) :: 가장 큰 원판을 먼저 C에 옮겨야한다. 즉, 위쪽원판 ( 나중에 쌓인 원판 )을 먼저 보조기둥에 옮겨야한다.

2. ( 재귀방식 ) :: 하나를 옮기면 N-1개 의 원판의 상황이 된다. 

 

결과적으로 Source( 초기 ) 기둥에서 Destination( 목적 ) 기둥으로 원판을 옮길때,

최하층 원판을 옮긴 상황은 N-1 개의 원판을 옮겨야할 때의 상황과 같고,

Source 와 Auxilary( 보조 ) 기둥이 바뀐 상황인 것이다.

이때, 최하층을 제외한 원판을 옮기는 횟수 1, 최하층 원판을 옮기는 횟수는 1

총 2회를 움직이면 N-1 일떄 옮기는 횟수만 남는 방식이다.

즉 맨 마지막 원판을 옮기기 위해서는 2회를 움직여야하므로 2N 비율로 상승하며,

1개의 원판일때는 예외적으로 1회를 옮기므로 2(N-1) +1 이라는 방정식이 도출된다.

이를 다 더한 값이 전체 이동횟수이므로 각항이 2N-1 방정식을 따르는 등비수열이다.

 

정리하면 N번째 밑의 원판을 옮기기 위한 동작은 2N-1

전체 N개의 원판을 옮겨야 하므로 각 N번쨰 원판동작을 합치면,

이는 등비수열이므로 2^N +1, 즉 O(2^N)라는 빅오를 따르게된다.

 

pseudo code 로 정리하면

 

func( n ) {

 return ( n == 1 ? 1 : func( n -1 ) + 1 )

}

 

아래의 테스트에서 확인해보자.

 

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서