[스위프트:알고리즘] 이진 탐색[3 / 3]: Binary Search: 이진 탐색: 프로토콜 지향으로 구현하기

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

저는 Swift 와 iOS 를 공부하고 연구하는 학생입니다.

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

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

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

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

---

• Swift version : Swift 4.2  Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘
• Youtube
• 칸 아카데미

• 씩이 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: )
• [스위프트 : 자료구조] 스택: Stack: 자료구조: DataStructure: 쌓기
• [스위프트 : 자료구조] 스택 : Stack : 프로토콜 지향 스택 구현하기
• [스위프트 : 자료구조] 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• [스위프트 : 자료구조] 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• [스위프트 : 자료구조] 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• [스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• [스위프트 : 자료구조] 큐: Queue: 프로토콜 지향 큐 구현하기
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐
• [스위프트:자료구조] 트라이: Trie: 문자열 찾기: 단어 찾기
  

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

• 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: #표현방식: #왜필요해?: #효율적: #간결성: #생략
• [스위프트 : 기초] 서브스크립트 : Subscript : 지름길
  
  
  

이진 탐색 : Binary Search [3 / 3]

이진 탐색 프로토콜 지향으로 구현해서 추상화 시키기

스위프트에서 이진 탐색을 구현하기 전에 알아야 할 2가지

• RandomAccessCollection 프로토콜을 채택한 객체이어야 한다는 것.
• RandomAccessCollection 은 Collection 중에서 index 계산이 가능한 것들을 말해 
• 예를 들면 우리가 사용하는 배열(Array 구조체) 이 RandomAccessCollection 의 대표적 예시지.
• 그 컬렉션은 정렬된 상태이어야 한다는 것.

프로토콜과 Collection 타입에 대해서 간략하게^^

• 프로토콜 자체를 모른다면 이번 주제는 그냥 넘어가길 바래! 하지만 알고시다면 여기! , 스위프트 공식문서 프로토콜은 여기
• 아래 그림은 스위프트 Standard Library 의 구조체들이 어떤 프로토콜을 채택하고 있는지 마인드 맵으로 정리한 거야
• 프로토콜의 가로축은 상속관계야.
• Sequence 를 상속받은게 Collection, 이를 상속받은데 BidirectionalCollection, 이를 상속받은게 RandomAccessCollection, 이를 상속받은게 RangeReplaceableCollection 인 식이지.
• Array 구조체는 RangeReplaceableCollection 까지 채택하고 있으므로 모든 Collection의 기능들을 사용할 수 있다고 볼 수 있어!

프로토콜 지향으로 구현한 이진 탐색

public extension RandomAccessCollection where Element: Comparable {
    // Comparable 은 Element 가 String 이나 Int 처럼 비교할 수 있는 타입이어야 한다는 뜻.
    func binarySearch(for value: Element, in range: Range<Index>? = nil) -> Index? {
        // 특정 범위에서 찾을때 Range 타입을 사용. 
        // Range 구조체의 제네릭을 이용해서 Index 타입을 설정
        // Index 는 Collection 프로토콜의 index 타입을 말하는 것
        let range = range ?? startIndex..<endIndex 
        // 매개변수가 nil 이면 RandomAccessCollection 을 채택한 타입(배열)의 startIndex, endIndex 로 범위 정해줌.
        guard range.lowerBound < range.upperBound else { return nil } 
        // 0 ..< 4 뒤에께 큰지 체크 하는 동시에 배열에 없는 값 입력시 종료조건.
        // 재귀호출에서 입력값 변화는 range 거든? 찾는 값이 없다면 range 가 작아질 때까지 작아져서 
        // range.lowerBound == range.upperBound 이 되겠지?  종료조건2
        let size = distance(from: range.lowerBound, to: range.upperBound)
        let middle = index(range.lowerBound, offsetBy: size / 2) // 중간 인덱스를 반환해줌
        // index 메소드 : 앞의 매개변수가 Collection 의 시작값.
        // 뒤의 매개변수가 시작으로 부터의 거리. 즉 0부터 시작해서 거리가 3 이면 3, 2부터시작해서 거리가 3 이면 5.
        if self[middle] == value { // 재귀호출 종료조건1
            return middle // 찾으려하는 value 의 인덱스 반환해줌.
        }else if self[middle] > value { // 여기서 self는 RandomAccessCollection 을 채택한 것의 인스턴스.
            return binarySearch(for: value, in: range.lowerBound..<middle) 
            // 왼쪽으로 탐색, range 에 변화를 줌.
        }else {
            return binarySearch(for: value, in: index(after: middle)..<range.upperBound) // 오른쪽
        }
    }
}

• 이진 트리의 아이디어는 반복문이나 재귀호출이나 모두 동일하다는 거!
• RandomAccessCollection  프로토콜을 extention 을 사용해서 확장하고 함수를 구현했는데
• 이는 이 프로토콜을 채택한 객체들은 모두 이 함수를 사용할 수 있게 된다는 뜻이야.
• 배열이 RandomAccessCollection 프로토콜 채택한 구조체니까 이제 배열의 모든 인스턴스에서 binarySearch 메소드를 사용할 수 있게 되.
• where 키워드를 사용해서 Element 가 Comparable 프로토콜을 채택한 것으로 범위를 설정했는데
• Int 나 String 같이 < or > or == 이러한 연산자들을 사용할 수 있는 타입들은 모두 Comparable 을 채택한 것들이야.
• 이 범위를 적용해 줌으로써 self[middle] == value 라는 '==' 기호를 쓸 수 있는거야.
• Range 구조체는 RandomAccessCollection 을 채택한 구조체중 하나이므로 RandomAccessCollection 내부에 작성 가능
• index(:offset:) 메소드는 RandomAccessCollection 프로토콜에 있는 메소드이므로 사용 가능.
• 특정 구간 부터 두번째 매개변수 까지의 인덱스 반환해주는 메소드임
• 나머지는 반복문, 재귀호출과 동일하므로 생략^^

실행과 결과

• 프로토콜로 구현한 함수 실행시 배열 인스턴스인 array 에서 바로 메소드를 호출하는 것을 볼 수 있쥬?
• 범위도 Range 구조체를 사용해서 0..<3 이런식으로 넣을 수 있게 됬지?
• 이렇게 편리한 메소드를 RandomAccessCollection 프로토콜을 채택한 타입이면 모두 사용할 수 있게 추상화시킨것
• 이게 프로토콜의 강점^^

• [스위프트:알고리즘] 이진 탐색[1 / 3]: Binary Search: 이진 탐색이 뭐야?
  
• [스위프트:알고리즘] 이진 탐색[2 / 3]: Binary Search: 이진 탐색: 반복문, 재귀호출로 구현하기

전체 소스 코드