ℹ️ 개요 : 파라메트릭 서치(Parametric Search)
결정 문제(결정 알고리즘)을 활용해 최적화 문제을 해결하는 알고리즘 설계 기법 중 하나이다.
- 최적화 문제(Optimization Problem) : 계란이 깨지지 않는 가장 큰 X는 얼마인가?
- 결정문제(Decision Problem) : X 층에서 계란을 떨어뜨리면 계란은 깨지는가?
결정 알고리즘은 이진 탐색을 사용하며, 이분법(Bisection Method)기반 방법으로 구하고자 하는 답을 반복해서 조정하여 구한다.
🚩 파라메트릭 서치가 동작하는 곳
연속된 구간 내에서 답이 분명이 존재할 때 파라메트릭 서치를 활용할 수 있다. 즉, 연속된 구간이라 하면 문제에서 활용되는 범위 내의 수 혹은 어떤 것들이 빠짐없이 정렬되어 있어야 한다.
위에서 예시로 든 계란 문제에서 계란이 깨지지 않는 가장 큰 X 기준으로 아래층에서는 계란을 떨어뜨려도 깨지지 않고, 위층에서는 계란이 깨지게 된다. 이와같이 연속된 구간(층)에서 결정 문제의 답이 바뀌게 되는 특정 지점을 찾는 것이다. 즉, 답이 반드시 존재하는 구간에서 구간의 범위를 재귀적으로 좁혀나가며 답을 찾는다.
다음과 같은 조건을 충족한다면, 파라메트릭 서치를 이용해 문제를 풀 수 있다.
- 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우
- (최소값을 구하는 경우) 최솟값이 x라면, x이상의 값에 대해서는 모두 조건을 만족
- (최대값을 구하는 경우) 최대값이 x라면, x이하의 값에 대해서는 모두 조건을 만족
📺 파라메트릭 서치 예제 : First Bad Version(LeetCode 287)
1 ~ n 번의 번호가 부여된 제품이 있을 때, k번 이후로는 전부 불량 제품이다. 이때 k를 찾는 문제
- 결정문제 : isBadVersion(version) → n번이 불량인가?
- 최적화 문제 : firstBadVersion(n) → 불량인 n의 최소값은 무엇인가?, 이진 탐색의 로직을 활용한다.
def firstBadVersion(n):
low, high = 1, n
while low < high:
mid = (low+high)//2
if isBadVersion(mid):
high = mid
else:
low = mid + 1
return low📚 REFERENCE
이진탐색(Binary Search)와 파라메트릭서치(Parametric Search)
Grow Exponentially