공기업 AI면접 하노이의 탑 꿀팁

방법
* 1번 탑 : 가장 크기가 작은 탑 / 2번 탑 : 그 다음으로 크기가 작은 탑 / 3번 탑 : 크기가 가장 큰 탑
1. 옮기고 싶은 탑의 개수가 홀수[짝수]일 때 첫 탑(1번 탑)은 가고 싶은 곳[가고 싶지 않은 곳]으로 이동
2. 2번 탑을 나머지 빈 공간에 이동시킨다
3. 1번 탑을 2번 탑 위로 옮긴다
4. 빈 공간에 3번 탑을 이동시킨다
5. 다시 1. 을 따라한다. (1번 탑을 가고 싶지 않은 곳으로 이동)
6. 2번 탑을 3번 탑 위에 올린다.
7. 1번 탑을 2번 탑 위에 올린다. 

​4단 탑의 경우
3개의 탑 + 1 로 생각하면 됨.
옮기고 싶은 탑의 개수가 4개일 때와 3개일 때로 경우가 나뉘게 됨.

​꿀팁
기본적으로 3단 연습이 되어있어야 함.
3단 이상의 탑을 옮겨야 하는 경우 옮겨야 하는 탑의 개수를 명확히 인지하고 옮겨야 함.

최소 이동경로
탑이 3개일 때 : 2^3-1=7
탑이 4개일 때 : 2^4-1=15
탑이 5개일 때 : 2^5-1=31

​ 참고자료
https://youtu.be/UF-EtEtiaPE