일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 백준
- OSI
- Java
- c언어
- 암호수학
- 스택
- 시간복잡도
- windosws wbcs
- pwnable.kr
- level13
- 파일 시스템
- 미로 탐색 알고리즘
- windosw 문자열
- 자료구조
- 정렬 알고리즘
- HTML
- 파이썬
- System
- 두근두근 자료구조
- 큐
- LoB
- 재귀
- ftz
- C
- ftz level13
- web
- War Game
- PHP
- SWiFT
- Stack
- Today
- Total
나의 기록, 현진록
[Swift] Data Structure recursion / hanoi / 자료구조 순환, 재귀 / 하노이 탑 본문
[Swift] Data Structure recursion / hanoi / 자료구조 순환, 재귀 / 하노이 탑
guswlsdk 2021. 7. 8. 13:17
<하노이 탑의 설명>
고대 인도의 베나레스에는 세계의 중심이 있고, 그 곳에는 아주 큰 사원이 있었다. 이 사원에는 높이 50cm 정도 되는 다이아몬드 막대 3개가 있는데, 그 중 한 막대에는 천지 창조 때에 신이 구멍이 뚫린 64장의 순금으로 된 원판을 크기가 큰 것부터 아래에 놓이도록 하면서 차례로 쌓아 놓았다. 그리고 신은 승려들에게 밤낮으로 쉬지 않고 한 장씩 원판을 옮기어 빈 다이아몬드 막대 중 어느 한 곳으로 모두 옮겨 놓도록 명령하였다...................................
조건
1. 한 번에 하나의 원판만 이동할 수 있다.
2. 맨 위에 있는 원판만 이동할 수 있다.
3. 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.
4. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.
위 조건을 기반으로 A, B, C 3개의 막대와 원판 3개를 A에서 C로 옮기는 과정이다.
해결 방안
A는 from
B는 tmp
C는 to라고 할 때
1. from의 맨 밑의 원판을 제외한 나머지 원판을 tmp로 옮긴다.
2. from에 남은 한 개의 원판을 to로 옮긴다.
3. tmp에 원판을 to로 옮긴다.
A 막대에 있는 원판들을 C로 옮겨야 할 때 n-1번째까지의 원판을 B에 임시로 옮겨두고 n번째 원판을 C에 옮기면 된다.
func hanoi(_ n: Int, _ from: Character, _ tmp: Character, _ to: Character){
if n == 1{
print("원판 1을 \(from)에서 \(to)로 옮긴다.")
}
else{
hanoi(n-1, from, to, tmp) //1
print("원판 \(n)을 \(from)에서 \(to)로 옮깁니다") //2
hanoi(n-1, tmp, from, to) //3
}
}
hanoi(4, "A","B","C")
2번은 if n==1 에서 해결이 되기 때문에 1, 3번만 고민하면 될 것이다.
1. from의 맨 밑의 원판을 제외한 나머지 원판을 tmp로 옮긴다.
hanoi(n-1, from, to, tmp)
3. tmp에 원판을 to로 옮긴다.
hanoi(n-1, tmp, from, to)
'Programming > Algorithm & Data Structure' 카테고리의 다른 글
[Swift] 프로그래머스 코딩테스트 연습 > 스택/큐 > 기능개발 (0) | 2022.05.11 |
---|---|
[Swift] 백준 10829 이진수 변환 / 재귀 /recursion (0) | 2021.07.22 |
[Swift] Data Structure Recursion / Fibonacci / 자료구조 재귀, 순환 / 피보나치 수열 (0) | 2021.07.07 |
[Swift] Data Structure divide and conquer, D&C / power / 자료구조 분할정복 / 거듭제곱 계산 (0) | 2021.07.06 |
[Swift] Data Structure recursion / divide and conquer, D&C / 자료구조 순환, 재귀 / 분할정복 (0) | 2021.07.06 |