1. 들어가며
재귀 알고리즘 중에 유명한 하노이탑 알고리즘을 이해해보겠습니다.
혼자서 오랜 고민 끝에 이해가 잘 되지 않아 유투브 영상과 블로그를 참고하여 이해했습니다!
2. 문제 소개
하노이 탑은 프랑스의 수학자 에두아르 뤼카가 1883년 소개한 유명한 문제로, 아래 그림을 보시면 익숙할 것이라고 생각이 듭니다. 옮기는 과정에서 작은 원반 위에 큰 원반이 놓일 수 없으며, tower 1에 있던 모든 원반이 tower 3으로 이동을 시키는 문제입니다.

3. 아이디어
어떻게 정의해야할지 잘 떠오르지 않아서 실제로 원반을 하나씩 옮겨보았습니다.
문제를 작게 만드어 해결하고 이후에 확대하는 방법이 알고리즘 문제를 푸는데 도움이 될 수 있습니다.
일단 3개의 원반을 A에서 C로 이동을 한다고 가정합니다.

세개을 원반을 이동할 때 얻을 수 있는 아이디어 세 가지가 있습니다.
1. 원반이 한 개 일때는 그냥 목표지점으로 이동을 하고 끝난다.
2. 가장 큰 마지막 원반이 목표 지점에 도달하게 되면 그 원반을 더 이상 이동을 하지 않는다.
3. 시작과 목표 원반이 아닌 보조원반에 가장큰 원반을 제외하고 모든 원반이 이동이 되는 과정이 있다.
->이 때 재귀 함수를 사용할 수 있다. 재귀함수에서 시작지점의 원기둥을 바꾸는 조작이 필요하다.
4. Pseudo Code
def hanoi(원반개수, 시작, 끝, 보조)
if 원반이 하나일 때:
#시작에서 끝으로 한 번 이동시킨다.
print(시작, 끝)
return
else:
#원반개수-1만큼 보조 원기둥으로 이동시켜야한다
hanoi(원반개수-1, 시작, 보조, 목표)
#이동시킨다.
print(시작, 보조)
#보조 원기둥에 있는 원반을 목표 원기둥으로 이동시켜야 하기 때문에 보조기둥을 시작기둥으로 변경한다.
hanoi(원반개수-1, 보조, 목표, 시작)
5. 간단 설명정리
하노이 탑 알고리즘은 3단계로 요약할 수 있습니다.
1. 원반(n)이 한 개일 때는 시작에서 목표로 간다.
2. n>1 일 때는 마지막 원반을 제외한 n-1 개의 원반을 보조기둥으로 옮긴다.
(+ 마지막원반은 (1)에 따라 목표기둥으로 이동한다)
3. n-1개의 원반을 목표기둥으로 옮긴다.
이 세 가지만 염두한다면 하노이 탑 알고리즘을 이해하는데 도움이 될 것 같습니다ㅎㅎ
6. 출처
https://shoark7.github.io/programming/algorithm/tower-of-hanoi
'Algorithm' 카테고리의 다른 글
[완전탐색] 백준 1476번: 날짜 계산 (0) | 2021.01.01 |
---|---|
[선택] 백준 11004번 K번째 수 시간초과 에러 (0) | 2020.08.04 |
[분할정복] 백준 11729번 출력초과 에러 해결방법 (0) | 2020.07.28 |
[분할정복] 백준 11729번 하노이탑 파이썬 풀이 (0) | 2020.07.28 |
알고리즘 공부 시작! (0) | 2020.07.28 |