[스위프트 : 알고리즘] 재귀 : 하노이의 탑 (5 / 6) : Hanoi: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  ( 18.09. 01 ~ ) Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘

• 씩이 Github
• 자료구조 소스파일 있습니다.
• iOS 관련 자료들, 정보들 정리해 두었습니다.

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• Swift4: 스택: #Stack: #자료구조: #DataStructure: #쌓기
• [스위프트 : 자료구조] 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• [스위프트 : 자료구조] 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• [스위프트 : 자료구조] 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• [스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐

• 스위프트로 구현한 알고리즘 : Algorithms in Swfit4
• [스위프트 : 알고리즘] 재귀호출 (1 / 6) : recursive: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 팩토리얼 (2 / 6) : factorial: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 거듭제곱 (3 / 6) : Power: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 피보나치 수열(4 / 6) : Fibonacci: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 하노이의 탑 (5 / 6) : Hanoi: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 최대공약수 (6 / 6) : GCD: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수

• Swift 주제별 분류
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략

재귀 : 하노이의 탑: Hanoi (5 / 6) in Swift4

• 하노이의 탑이 뭐야?
• by khanacademy
  

세 개의 축과 $$nn개의 원반이 주어지는데 각각의 원반은 크기가 상이합니다. 축을 A, B, C라고 부르기로 하고 원반은 가장 작은 원반을 1로, 가장 큰 원반을 $$nn이라고 번호를 매긴다고 합시다. 처음에는 모든 $$nn개의 원반이 크기 순서대로 위에서 아래로, 즉 1이 가장 위에, 그리고 $$nn이 가장 아래인 상태로 축 A에 놓여 있습니다. 원반이 $$n = 5n, equals, 5개인 하노이 탑은 다음과 같습니다.

목표는 모든 $$nn개의 원반을 축 A에서 축 B로 옮기는 것입니다.

쉬워보이죠? 그렇지만 그렇게 쉽지는 않은데, 다음 두 가지 규칙을 지켜야 하기 때문입니다.

1. 한 번에 하나의 원반만 움직일 수 있습니다.
2. 자신보다 작은 원반이 그 아래에 놓일 수 없습니다. 예를 들어 원반 3이 축에 있다면 원반 3 밑에 있는 원반은 모두 3보다 큰 숫자로 되어 있어야 합니다.

원반이 두 개일 경우는 어떨까요? $$n = 2n, equals, 2일 경우는 어떻게 문제를 풀 수 있을까요? 3단계로 풀 수 있습니다. 아래는 시작할 때의 상태입니다.

먼저 원반 1을 축 A에서 축 C로 옮깁니다.

축 C를 나머지 축으로 이용하여 원반 1을 잠시 꽂아놓음으로써 원반 2를 꺼낼 수 있게 합니다. 이제 가장 바닥에 있던 원반 2가 위로 나왔습니다. 이것을 축 B로 옮깁니다.

마지막으로 원반 1을 축 C에서 축 B로 옮깁니다.

이 해법은 3단계로 이루어집니다. 다시 한번 말하지만 두 개의 원반을 꼭 축 A에서 축 B로 옮기지 않아도 됩니다. 축 A를 나머지 축으로 이용하고 축 B에서 축 C로 옮겨도 됩니다. 원반 1을 축 B에서 축 A로 옮긴 후 원반 2를 축 B에서 축 A로 옮기고 마지막으로 원반 1을 축 A에서 축 C로 옯깁니다.

• 하노이의 탑 문제해결 과정
• 원판이 5개라고 합시다. A 축에서 B 축으로 옮긴다고 합시다. 
• 원판 5를 옮기려니까 위에 원판 4개가 있네?
• 원판 4개를 옮기려니까 위에 원판 3개가 있네?
• 원판 3개를 옮기려니까 위에 원판 2개가 있네?
• 원판 2개를 옮기려니까 위에 원판 1개가 있네?
• 1개 먼저 옮기자!  
• 재귀의 아이디어인 가장 작은 범위의 문제부터 해결한다. 맞죠? 기억안나면 여기
• 가장 위의 원판 1 은 종료조건 이기도 합니다.
• 아래 그림은 구현할 때 재귀를 두 번 수행해야 한다는 것을 보여줍니다.

• 재귀호출 요구사항 재귀호출에 대해 모른다면 클릭
• 재귀의 호출은 문제 내에서 범위가 점점 작은 방향, 즉 하위문제에 대해 이루어 져야 한다.
• 재귀 호출은 더 이상 반복되지 않는 종료 조건이 있어야 한다.

• 구현 : hanoi
• 재귀호출로 구현한 하노이의 탑
• 원판이 한개여서 (n = 1) 위에 다른 원판이 없는 경우가 재귀호출의 종료조건이 됩니다. -> 요구사항 1 만족
• 재귀호출로 매개변수에 n - 1 입력되쥬? 작아지므로 - > 요구사항 2 만족

public func hanoi(diskNum n:Int,from: Character,to: Character,by: Character) {
    if n == 1 { // 종료조건 (n = 1 이 문제 범위에서 가장 작은 단위)
        print(" 원반 1 을 \(from) 에서 \(to) 로 이동.")
    }else {
        hanoi(diskNum: n-1, from: from, to: by, by: to) // a 축에서 c 축으로 원판들 이동시키자!
        print(" 원반 \(n) 을 \(from) 에서 \(to) 로 이동.") // 위에 아무것도 없으니 젤 무거운 놈 b 축으로 이동시키자!
        hanoi(diskNum: n-1, from:by , to: to, by: from) // c 에 있던 원판들 b 축에 다시 쌓자!
    }
}

• 실행 과 결과

• 수행속도
• 위에 문제해결과정 에서 보이는 그림에서 원판 개수별 연산 수행 횟수가 나옵니다.
• 1 -> 3 -> 7 -> 15 -> ... 증가하네요. 2^(n-1) 로 증가하네요?
• 성능은 O(2^n) 인 개쓰레기 알고리즘 이지만.. 재귀를 표현하는 아주 훌륭한 문제임은 확실하네요. 

• Helper 메소드 ( 궁금하실 까봐^^.. ) 

public func example( description:String, excute:()->() ) {
    print("---Example of \(description)---")
    excute()
}
 
public func processTime(blockFunction: () -> ()) -> Float { 
    let startTime = CFAbsoluteTimeGetCurrent() 
    blockFunction() 
    let processTime = CFAbsoluteTimeGetCurrent() - startTime 
    return (Float(processTime))
}

전체 소스 코드