-
[스위프트:알고리즘] 이진 탐색[1 / 3]: Binary Search: 이진 탐색이 뭐야?스위프트: Swift/알고리즘 : Algorithms in Swift 2018. 10. 16. 19:12
안녕하세요 ! 씩이 입니다!
저는 Swift 와 iOS 를 공부하고 연구하는 학생입니다.
같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.
제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.
공유가 미래 라고 생각합니다.
한국의 모든 개발자분들 존경합니다!
- Swift version : Swift 4.2 Swift 언어
- 참고한 것들
- 씩이 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 [1 / 3]
이진 탐색이 뭐야?
- 이진 탐색은 O(log n) 의 시간복잡도를 가지는 가장 효율적인 탐색 알고리즘 중 하나야.
- 이진 트리에서 노드를 탐색할 때 트리가 balanced 한 경우에 시간 복잡도가 O(log n) 이었지? unbalanced 하고 최악의 경우 O(n) 이었고 궁금하다면 여기
- 이렇게 효율적이니까 실시간으로, 스스로 balanced 하게 만드는 트리도 구현했었잖아. AVL Tree 궁금하다면 여기
이진 탐색이 가능하려면 어떤 조건이 필요해?- 값이 정렬된 상태의 Collection 이어야 해
- Collection 프로토콜 이름으로 스위프트의 배열( Array ) 은 대표적인 Collection 타입중 하나야 .
- 프로토콜을 잘 모른다면 넘어가도 되지만 스위프트는 프로토콜 지향 프로그래밍 언어기 때문에 마지막에는 프로토콜 지향 이진 탐색도 구현할거야.
이진 탐색이 얼마나 효율적인데 ? ( 일반 탐색과 비교 )- 일반 탐색과 이진탐색을 비교하면 이진 탐색이 얼마나 효율적인지 쉽게 이해될거야.
- 아래 배열에서 '31' 을 탐색하려고 하면
- 일반 탐색의 경우 8번의 비교연산을 수행하고
- 이진 탐색의 경우 단 3번만의 비교 연산만으로 값을 찾아냄을 알 수 있어. 굿 ( 단, 정렬된 상태 이어야 한다는 것 잊지 않기! )
일반 탬색
이진 탐색
이진 탐색의 아이디어- 1. 중간 인덱스를 찾고
- 2. 찾으려는 값과 중간 인덱스의 값을 비교한 후
- 3. 찾으려는 값이 중간 인덱스의 값과 일치하면 중간 인덱스를 반환 ( return )
- 3. 찾으려는 값이 중간 인덱스의 값보다
- 크면 배열에서 중간 인덱스 이후의 인덱스들로 범위를 좁혀서 반복 or 재귀 호출
- 작으면 배열에서 중간 인덱스 이전의 인덱스들로 범위를 좁혀서 반복 or 재귀 호출
- 위의 배열로 적용해보면 아래와 같겠지?
'스위프트: Swift > 알고리즘 : Algorithms in Swift' 카테고리의 다른 글
댓글
