🔬 Parametric Search

🐧 최적화 문제를 여러번의 결정문제(예 혹은 아니오)로 바꾸어 이분탐색으로 해결하는 기법

 

→ 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 - 여기서 최적화란, 어떤 값을 최대한 높이거나 낮출 때 사용

 

🐧

① Parametric Search로 구하고자 하는 값을 이분탐색으로 증/감 바꾸며 YES/NO 여부 확인

 

② 결정문제를 만족하고 만족하지 않음에 따라 이분탐색 범위를 end를 mid-1 또는 start를 mid+1로 설정해 절반으로 줄임

 

★ 탐색의 범위가 log2N씩 줄어드므로 1억이 넘어가는 범위라 하더라도 매우 효과적인 시간 내에 탐색 가능 ★

왼쪽 그림과 같이 일정한 방향으로 두 변수의 관계가 있어야 한다 / 오른쪽 그림과 같이 일정한 방향이 아니면 x

---

① BOJ 3079 입국심사(골드5)

: 입국심사대의 개수가 주어지고, 방문한 인원 M이 주어진 상태에서 입국심사를 받는 시간 x의 최솟값을 구하는 문제

→ 소요시간을 x, 해당 소요시간 내에 수용할 수 있는 최대인원을 y라 하면 x와 y는 비례 관계

→ x를 줄이면서 해당 y값이 방문한 인원 M을 수용할 수 있는 지(즉 y≥M) 확인: 즉 이분탐색으로 x를 찾으면서 y≥M인 최소 x 탐색

 

② BOJ 2110 공유기 설치(골드4)

: 집의 좌표가 주어지고(중복 x) 공유기 개수 C가 주어진 상태에서 공유기를 가진 집 사이의 거리 x의 최댓값을 구하는 문제

→ 공유기를 가진 집 사이의 최소 인접 거리를 x, 설치할 수 있는 공유기의 개수를 y라 하면, x와 y는 반비례 관계

→ x를 줄이면서 그리디로 구한 y가 주어진 공유기의 개수 C보다 크거나 같은 지 확인: 즉 이분탐색으로 x를 찾으면서 y≥C인 최소 x 탐색

(왜 첫번째 집부터 y 측정을 시작하는지 증명 필요)

 

③ BOJ 2343 기타 레슨(실버 1)

: 강의의 길이가 주어지고 블루레이의 개수 M이 주어진 상태에서 여러 묶음합의 최댓값 블루레이의 크기 x 최솟값을 구하는 문제

→ 블루레이의 크기를  x, 블루레이의 개수를 y라 하면 x와 y는 반비례 관계

→ x를 줄이면서 그리디로 구한 y가 주어진 블루레이의 개수 M보다 작거나 같은 지 확인: 즉 이분탐색으로 x를 찾으면서 y≤M인 최소 x 탐색

: 그림을 그리고 비례/반비례 관계 확인 → 가능/불가능 영역 확인 → ans update 케이스 확인

 

🐧 정리

① 최적의 값을 구하고자 하는 x / 이에 따라 한방향으로 증/감하는 y 확인(y를 파악하는게 어려움)

→ x기반 y를 구하는 과정에서 greedy 알고리즘 사용되기도 함

→ 또한 x와 y가 한 방향으로 흐르는 비례/반비례 관계인지도 파악해야 함. 해당 관계가 성립이 안된다면 이분탐색 불가능 

② 이분탐색의 start, end 적절히 정하기(start와 end 모두 문제의 조건을 만족하는 최솟값, 최댓값으로 설정)

③ Yes/NO인 경우의 이분법적인 상황을 정확히 기억하고 두 상황 중 답이 가능한 상황일 때 ans 주기적 update

④ 최종 ans 변수 출력

---

BaaaarkingDog