[TIL] 매개 변수 탐색 Parametric Search

2805 나무 자르기 문제에서 매개 변수 탐색을 이용해서 풀었기에 정리해본다 

매개 변수 탐색 Parametric Search

최적화 문제를 결정 문제로 풀 수 있는 알고리즘으로,
조건을 만족하는 최소값 또는 최대값을 찾는 방법 

 

* 최적화 문제 - 어떤 알고리즘의 최적 솔루션을 찾는 문제 

* 결정 문제 - 답이 이미 결정되어 있다고 보고 문제를 푸는 방식 

 

이분 탐색과의 차이점

이분 탐색 공부 자료 

이분 탐색은 배열에서 Target 과 일치하는 값을 찾으면 바로 함수를 종료한다

반면, 매개 변수 탐색은 함수를 종료하지 않고 모든 배열을 탐색하며

조건을 만족하는 가장 크거나 작은 값을 찾는다 

1. 어떤 시점까지 조건을 만족하지만 그 후로 만족하지 않는 경우, 조건을 만족하는 최대값 찾기 
2. 어떤 시점까지 조건을 만족하지 않지만 그 후로는 조건을 만족하는 경우, 조건을 만족하는 최소값 찾기 

 

그리고 이분 탐색과 동일하게, 배열이 정렬되어 있어야 사용 가능하고

시간 복잡도도 동일하게 O(logN) 이다 

 

 

1. 매개변수 Param

2. 결정함수 fn(param) 가 중요하고, 이는 이분 탐색과 매개 변수를 함께 사용하는 방식으로 볼 수 있다 

 

양이 너무 적어서 이분 탐색이랑 같이 포스팅할걸 그랬다