Algorithm/이분탐색
매개 변수 탐색 (Parametric Search)
jusung-c
2022. 5. 1. 21:05
Up-Down 게임
- A가 1~1000 사이 어떤 자연수를 선택
- B는 A에게 "생각한 숫자가 X 이상이야?" 라는 질문 가능
- A는 맞으면 1, 아니면 0 대답
- 최소 횟수로 질문하려면?
방법 1) Linear Search
1부터 1000까지 전부 물어보기
"생각한 숫자가 1 이상?"
"생각한 숫자가 2 이상?"
...
"생각한 숫자가 1000 이상?"
-> 마지막 Yes인 대답이 정답!
최악의 경우 1000번 질문해야 한다. 더 빠른 방법은 없을까?
방법 2) Binary Search
A가 생각한 숫자를 매개변수로 생각해서 이분탐색으로 찾기
L=1, R=1000인 구간 L~R에서 이분탐색!
탐색할 범위의 중앙 값과 찾아야 할 숫자 K를 비교를 통해 정답이 가능한 구간 [L, R]을 좁혀나가면서 찾기
이 방법은 숫자의 범위가 1~N이라고 했을 때, 질문 횟수는 최대 log N번 이므로 총 O(log N)의 시간 복잡도를 가진다.
핵심)
- 정답을 매개변수로 만들고 이분탐색을 통해 찾아낸다.
- 이분 탐색은 항상 정렬된 상태에서 진행한다.
키워드)
문제에 최댓값, 최솟값을 구하라고 할 경우 Parametric Search 접근을 시도해볼 가치가 있음.