반응형
https://programmers.co.kr/learn/courses/30/lessons/12946
코딩테스트 연습 - 하노이의 탑 | 프로그래머스
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다. 한 번에 하나의 원판만 옮길 수 있습니다. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 하노이 탑의
programmers.co.kr
재귀호출의 가장 유명한 예시인 하노이 타워.
3개의 탑이 있고, 각각 시작지점 a, 경유지점 b, 목적지점 c라고 정의한다.
n개의 탑이 있을 때, a에서 b를 거쳐 c로 모든 타워를 규칙에 맞게 이동시키는 방법을 재귀호출 문제로 푼다면
1. 위에서부터 n-1개의 원반을 a에서 c를 거쳐 b로 이동시킨다. 그래야 맨 마지막 원반을 원하는 목적지로 이동시킬 수 있다.
2. 맨 아래에 있던 가장 큰 원반을 a에서 c로 이동시킨다.
3. b로 이동시켰던 n-1개의 원반을 b에서 a를 거쳐 c로 이동시킨다.
1과 3은 시작지, 목적지, 경유지만 다를 뿐 함수 로직이 동일하기 때문에, 재귀호출 형태로 구현이 가능하다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 1697. 숨바꼭질 (0) | 2019.12.16 |
|---|---|
| [Python] 백준 1012. 유기농 배추 (0) | 2019.12.15 |
| [Python] 프로그래머스. 야근 지수 (Level 3) (0) | 2019.12.13 |
| [Python] 백준 1931. 회의실배정 (0) | 2019.12.10 |
| [Python] 백준 4195. 친구 네트워크 (0) | 2019.12.09 |