분할 정복(Divide and Conquer) 알고리즘 1 : 이진 탐색 (Binary Search)

A. 분할 정복 알고리즘

1. 이진 탐색 (Binary Search)

a. 이진 탐색이란?

🌟 정렬된 배열 또는 리스트에서 특정한 값을 찾는 알고리즘

 

배열이나 리스트가 정렬되어 있다는 가정하에 작동

 

b. 진행방식

1. 배열이나 리스트의 중간 요소를 선택하여 찾고자 하는 값과 비교
   
   1. 찾고자 하는 값이 중간 값보다 작으면 중간 값의 왼쪽 반을 대상으로 탐색을 수행
   2. 찾고자 하는 값이 중간 값보다 크면 중간 값의 오른쪽 반을 대상으로 탐색을 수행

 

이렇게 반복하여 탐색 대상이 하나가 될 때까지 이 과정을 반복

 

+ [게임 프로그래머 입문 올인원] 이진 탐색 70강 내용

 

이런 느낌 (Vector, 인덱스 기반으로 실행되기 때문에 위 코드로 list는 사용이 어려움)

 

실행하면 이렇다

 

c. 이진 탐색의 장단점

👍 장점

1) 선형 탐색에 비해 훨씬 효율적으로 동작

 

💙 선형 탐색이란?

선형 탐색은 찾고자 하는 값이 배열이나 리스트의 처음부터 끝까지 순차적으로 비교하면서 찾아나가는 방법

 

탐색 대상이 반으로 줄어들기 때문에 탐색 속도가 로그 시간복잡도 O(log n)로 감소

따라서 데이터 양이 많아도 빠르다

 

2) 추가적인 공간을 요구하지 않음

 

👎 단점

1) 배열이나 리스트가 정렬되어 있어야 함

 

2) 중간 삽입, 삭제가 느리다

 

하게되면 시간 복잡도는 O(N)

➡ map이 필요한 이유 

 

 

 

---

출처 : chatGPT, https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버