하노이타워 알고리즘

1. 개요

 - 하노이탑을 이해하면 보통 재귀함수를 완벽하게 이해할 수 있다고 한다.

 - 근데 솔직히 난 아직도 재귀가 낯설다. (더 파고들어가야할 듯)

 - 부분집합 출력하는 문제에도 재귀가 나오는데 부분집합 출력을 공부하면서 재귀가 잘 이해가지 않아서 하노이탑을 다시 살펴본다.

 

2. 문제

 - N사에서 물어본 문제로 기억함

 - HanoiTowerSol(5, 'A', 'B', 'C')인 경우 몇번 이동한 것일까?? 아래 해설 참고

3. 코드

4. 해설

HanoiTowerSol(1, 'A', 'B', 'C') 일 때 1번 이동이 있었음.(1번의 출력을 의미)

HanoiTowerSol(2, 'A', 'B', 'C') 는 HanoiTowerSol(1, 'A', 'B', 'C')을 2번 호출한다는 것을 알 수 있음.

즉, 2 + 1번의 출력이 발생!! 여기서 2는 HanoiTowerSol(1, 'A', 'B', 'C')를 2번 호출했을 때 출력발생!! 그리고 1은 아래 코드 상 14번 째 줄을 의미

HanoiTowerSol(3, 'A', 'B', 'C')는 HanoiTowerSol(2, 'A', 'B', 'C')을 2번 호출한다는 것을 알 수 있음.

즉, 6 + 1번의 출력이 발생!! 여기서 6은 HanoiTowerSol(2, 'A', 'B', 'C')를 2번 호출했을 때 출력발생!! 그리고 1은 아래 코드 상 14번 째 줄을 의미

이런 식으로 계산하면 규칙발견 가능!!

출력은 곧 이동을 의미하므로!!    (2^n) - 1번 이동이 발생한다. 

그래서 답은 31