하노이탑 알고리즘 : 재귀 호출의 대표적인 문제를 구현해 봅시다.
재귀 함수를 배우셨으니까, 제일 유명한 문제 중 하나인 하노이탑 알고리즘을 구현해 봐야 겠어요. 보통 하노이의 탑 문제는 기둥이 3개이고, 작은 기둥 위에 큰 기둥이 올 수 없다는 조건이 걸려있는 문제를 말해요. 또 한 번에 하나의 원판을 옮길 수 있는데요. 물론 백준에는, 기둥이 4개이 문제도 보입니다. 그건 논외로 합시다. 99xx번대에 있던 걸로 기억하는데 말입니다. 이걸 어떻게 구현하면 좋을까요? 생각보다 난이도가 조금 있어 보이는데요. 답은 재귀에 있습니다. 이 부분에 대한 내용은 관련 글에 충분히 설명이 되어 있으니, 개념 이해가 아직 안 되셨다면 보시고 오시는 게 좋아 보입니다. [관련글] 재귀 함수가 무엇일까요? 먼저 기저 조건을 봅시다. 옮길 원판의 갯수가 0개이면 어떤가요? 어떠한 연산..
자료알고/자료구조
2019. 7. 12. 01:42
최근댓글