코딩테스트 준비를 위한 과정

1. 이진 탐색

1.1 순차 탐색(Sequential Search)

1. 순차적으로 데이터를 탐색한다는 의미를 갖는다.
2. 데이터의 수가 N이라고 할 때, N번 비교를 하며 데이터를 찾기 때문에 시간 복잡도는 $O(N)$이다.

1.2 이진 탐색(Binary Search)

1. 내부 데이터들이 정렬되어 있어야만 사용 가능하다.
2. 데이터를 매우 빠르게 찾아낼 수 있다.
3. 데이터를 탐색할 때, 확인할 데이터의 수가 절반씩 줄어들어, 시간 복잡도가 $O(NlogN)$이다.
4. 구현 방법에는 재귀와 반복이 있다.
5. 출제되는 빈도가 꽤나 높으니 코드를 잘 외우두자.
6. 탐색 범위가 2000만을 넘어가거나 데이터의 수가 크면 이진 탐색처럼 $O(NlogN)$의 속도를 내는 알고리즘을 떠올리자.