하노이 타워 : The Tower of Hanoi
Programming/Data Structure 2012. 12. 24. 02:59 |하노이 타워 문제는 재귀함수의 힘을 보이는 대표적인 예로 꼽힌다.
재귀적으로 접근하지 않으면 해결이 쉽지 않은 문제이다.
하노이 타워의 조건
1. 원반은 한 번에 하나씩만 옮길 수 있다.
2. 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.
하노이 타워는 원반의 수가 늘어나도 해결방법에는 차이가 없다. 다만 원반의 수가 늘어날수록 일련의 과정을 더 많이 반복해야 할 뿐이다.
그래서 그 일련의 과정을 파악하면 해결할 수 있게된다.
원반 n개를 옮기는 과정
1. 작은 원반 n-1개를 A에서 B로 이동.
2. 큰 원반 1개를 A에서 C로 이동.
3. 작은 원반 n-1개를 B에서 C로 이동.
이렇듯 원반 n개를 이동하는 문제는 원반 n-1개를 이동하는 문제로 세분화되고, 또 원반 n-1개를 이동하는 문제는 원반 n-2개를 이동하는 문제로 세분화된다.
즉, 원반 n개를 이동하는 문제는 결국 원반 1개를 이동하는 매우 쉬운 문제로 세분화되는 것이다.
재귀함수를 정의하는데 있어서 반드시 생각해야 할 것은 재귀의 탈출조건이다.
그런데 n개의 원반 이동이 n-1개의 원반 이동으로 세분화되어서 재귀를 구성하게 된 것으므로 탈출의 조건은 다음과 같다.
"이동해야 할 원반의 수가 1개인 경우"
코드를 보면 너무나 간단해서 허탈한 기분이 든다. 이것이 재귀의 힘...
'Programming > Data Structure' 카테고리의 다른 글
배열을 이용한 리스트의 구현 (0) | 2012.12.24 |
---|---|
추상 자료형: Abstract Data Type (0) | 2012.12.24 |
이진 탐색 알고리즘의 재귀적 구현 (0) | 2012.12.23 |
재귀의 활용 : Fibonacci Sequence (0) | 2012.12.23 |
함수의 재귀적 호출 (0) | 2012.12.23 |