Binary Search

순차 탐색

• 데이터를 앞에서부터 하나씩 확인, 탐색의 기본
• count() 함수 등에 사용되며 많이 쓰임
• O(N)

이진 탐색

특징

• 리스트 내에서 데이터를 매우 빠르게 탐색할 수 있음

• 이진 탐색은 배열 내부 데이터가 정렬되어 있어야만 사용 가능

• 탐색 범위를 절반씩 좁혀감

• 시작점 s, 끝점 e, 중간점 mid 세 변수 사용

• 찾으려는 데이터와 mid 데이터를 비교하여 원하는 데이터를 찾는 과정

• 범위 좁힐 때 mid 자리는 포함하지 않도록 짜자!

• O(logN)

• 2 가지 방법 구현 가능

  • 재귀
  • 반복문

• 간단한 원리지만 코테에서 이진 탐색을 구현할 수 있는 사람은 10% 내외임. 무조건 여러 차례 직접 구현하면서 외울것

• 일반적으로 코테에서 이진 탐색 문제는 탐색 범위 크게 주는 경우가 많음, 데이터 개수가 1,000만을 넘거나, 검색 값 범위가 1,000억 이상이면 이진 탐색을 고려할 것

  → 이럴 때 입력 값은 반드시 sys.stdin.readline().rstrip() 해야 입력 시간 초과 안걸림

이진 탐색 트리

• 자료구조
• 이진 탐색을 지원해줌
• 두 자식을 가지며 왼쪽은 부모보다 작고, 오른쪽은 부모보다 큼
• 보통 이진 탐색 트리 자료구조를 구현하는 문제는 안나옴

부품 찾기 문제

N (1 ≤ N ≤ 10^6) 개의 부품의 정수 번호가 담긴 리스트에서 M (1 ≤ M ≤ 10^5) 개 원소를 찾는 문제. M 개 원소를 순차적으로 보며 찾는 부품이 있으면 'yes' 를 출력하고, 없으면 'no' 를 출력하라.

N = 5, [8, 3, 7, 9, 2]

M = 3, [5, 7, 9]

⇒ no yes yes

솔루션

1. 이진 탐색
2. 계수 정렬
   : 백만짜리 리스트를 만들어서 카운트 세고, 0 이 아니면 yes 출력.
3. set 사용
   : 부품 리스트를 set 에 넣어서 중복 제거 → 찾는 부품을 순차적으로 돌며 순차 탐색

파라메트릭 서치

• 최적화 문제 (최댓값 or 최솟값 찾기) 를 결정 문제 (O or X) 로 바꾸는 해결 기법
• 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 나옴
• 나는 시작점을 min 으로 잡았는데, 문제는 0 으로 잡음. 나처럼 하면 안되는건가?
  ⇒ m 이 클 경우 height가 원소들보다 작아질 수도 있기 때문에 0 으로 잡는게 맞음
• 파라메트릭 서치 문제는 반복문으로 해결
• 백준 나무자르기 문제 볼 것!

참조

• 이것이 취업을 위한 코딩테스트다 with Python 도서, 나동빈