Suhwanc

하노이 탑과 Stable Marriage

하노이 탑이란? 그림과 같이 세 개의 기둥과 이 기둥에 꽃을 수 있는 다양한 원판들이 있다. 이 탑은 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 기존에 있던 그대로 다른 기둥으로 옮겨서 다시 쌓아야한다. 조건은 다음과 같다 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다. 이 문제는 원판의 개수가 적을 경우는 머리로 쉽게 생각할 수 있지만 조금만 커져도 원판을 이동시키는 횟수가 급격하게 많아기지 때문에 생각만큼 쉽지 않다. 이 문제에 대한 해결방안은 알고리즘 설계 기법중 하나인 재귀(recursion)을 이용하는 것인데 방법은 다음과 같다. n=1 : 원판을 그냥 옮긴다 n=k 일 때 옮길 수 있다고 가정 한 후 n=k+1 일 때 (미리 가정한)..