CH2하노이타워(1)

02-3. 하노이 타워 : The Tower of Hanoi ①

이번시간에는 앞에서 몇번 강조한 하노이타워를 해결해보겠다.

재귀적인 사고를 해서 하노이타워를 해결하는게 처음보는 사람에겐 어려울 수 있다.

피보나치 수열로 돌아가보자. 함수에서 주어지는 초기 데이터는 0과 1밖에 없다. 0과 1에 특정한 연산을 하는 함수를 재귀적으로 호출해서 $n$번째 수열값을 구한다.

피보나치를 재귀적으로 구할 수 있는 이유는 $n$번째 수열값을 구하는 연산에 $n-1$번째 수열값을 구하는 연산이 포함되어있기 때문임.

연산의 포함관계와 초기데이터에 집중해서 풀어보자.

이때 앞서 말한 것 처럼 호출순서에는 관심갖지 말자. 결과를 구하는데에는 도움이 안되고, 호기심해결하는데는 매우 어렵다.

하노이 타워는 어렸을때 많이 해봐서 알지?

• 하노이타워에서 포함관계는, $n$칸까지 원반을 옮기려면 $n-1$칸짜리 원반을 옮기는 것을 포함하고 있다는 것임.

CH2하노이타워(2)

02-3. 하노이 타워 : The Tower of Hanoi ②

하노이타워의 논리는 다음과 같다.

막대 A에 꽂혀있는 $n$개를 막대 C로 옮기려면

1. 막대 A에 꽂혀있는 원반 $n-1$개를 B로 옮긴다.
2. 막대 A의 마지막 원반을 C로 옮긴다.
3. 막대 B에 있는 원반 $n-1$개를 C로 옮긴다.