[이분탐색] 파라메트릭 서치(개념)

파라메트릭 서치 문제는 단독 문제로 나오기보다는 다른 알고리즘과 결합해서 출제되는 것 같습니다.

파라메트릭 서치는 간단히 말하자면, (갓종만북의 표현을 빌려)

최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것

이라고 할 수 있습니다. 

지금은 이 표현이 와닿지 않을 수 있습니다. 간단한 그림을 통해 한 번 설명해보도록 하겠습니다. 

다음과 같이 나이순으로 정렬된 사람들이 있습니다. 그리고 25살 이상이라면 소주를 좋아한다는 것이 증명되어 있다고 합니다. 그럼 이 중에서 소주를 좋아하는 나이가 가장 어린 사람은 누구일까요?? 물론 가장 간단한 방법은 앞에서부터 차례대로 "너 소주 좋아하니?"라고 물어보면서, 처음으로 "네!"라고 대답하는 사람을 찾는 것일 겁니다. 하지만, 파라메트릭 서치를 이용해 최적화 문제를 결정 문제로 바꾼다면, log시간안에 문제를 풀어낼 수 있습니다. 이 문제라면, 최적화 문제와 결정 문제는 각각 아래와 같을 것입니다.

최적화 문제 : 소주를 좋아하는 나이가 가장 어린 사람 (즉, 각 사람을 위의 순서 그대로 배열에 저장한다고 한다면, 배열의 최솟값 이라고 할 수                      있겠죠?)

결정 문제 : "너 소주 좋아하니?" -> "네"(나이가 25세 이상이라면) 혹은 "아니오"(나이가 25세 미만이라면) 

그렇다면 누구에게 "너 소주 좋아하니?" 라고 묻는 것이 가장 현명할까요? 아직 사람들에 대해 아무 정보도 없으니 당연히 가운데의 사람이겠죠? 그래서 처음에는 D에게 소주를 좋아하냐고 묻겠습니다. 그리고, 전체 사람들 모두 아직은 정답의 후보가 될 수 있으니 L~R 범위를 전체로 지정해주도록 하겠습니다.

그런데, D가 소주를 좋아하지 않는다고 하네요! 그럼 소주를 좋아하는 사람들은 D보다 나이가 많은 사람들이겠죠? 즉, D를 기준으로 오른쪽에 위치한 사람들이라고 할 수 있습니다. 따라서, 우리가 처음에 지정했던 L~R 범위를 오른쪽으로 옮겨줘야합니다. 위와 같은 상황에선, L을 D의 오른쪽(mid+1)로 옮겨주면 됩니다.

그럼 다음으로는, 처음에 D에게 소주를 좋아하냐고 물었던 것과 같이, 정답이 될 수 있는 범위의 사람들(L~R) 중에 가운데에 위치한 사람에게 소주를 좋아하는지 물어보는 것이 현명하겠죠? 따라서 F에게 소주를 좋아하는지 물어보도록 하겠습니다.

오! F는 소주를 좋아한다고 하네요! 그럼 정답자(소주를 좋아하는 가장 어린 사람)는 F가 되는 것일까요? 잘 생각해보면, 저희는 아직 D와 F에게만 소주를 좋아하는지 물어봤습니다. 만약, E가 소주를 좋아하는 25살 이상의 사람이면 정답자는 E가 되겠죠? 즉, F가 소주를 좋아한다고 답하기는 했지만, 그것이 소주를 좋아하는 더 어린 사람이 없다는 것을 보장해주지는 못합니다. 따라서, L~R의 범위를 D와 F사이로 옮겨줘야 합니다. 여기선, R을 F의 왼쪽인 E로 옮겨주면 되겠죠?

마지막으로, E에게 소주를 좋아하는지 물어보도록 하겠습니다. 여기서 만약, E가 좋아한다고 답한다면 정답자는 E가 되고, 좋아하지 않는다고 답한다면 정답자는 F가 되겠죠?

아, E는 소주를 좋아한다고 합니다. 따라서, 정답자. 즉, 소주를 좋아하는 가장 어린 사람은 E가 된다고 할 수 있습니다.

위의 문제를 풀면서 어떤 알고리즘이 생각나셨나요? 파라메트릭 서치는 문제를 풀어나가는 과정이 바이너리 서치(이분 탐색)와 매우 흡사합니다. 파라메트릭 서치는 의외의 문제들에 적용돼서 최적화 문제들을 조금 더 쉽게 풀 수 있게 해줍니다. 파라메트릭 서치의 핵심은 결정 문제입니다. 해당값이 정답이 될 수 있는 값인지 아닌지를 쉽게 판단할 수 있어야(즉, 결정 문제를 쉽게 풀 수 있어야) 최적화 문제를 파라메트릭 서치로 풀 수 있습니다. 또한, 정답이 될 수 있는 값들이 연속적이어야 파라메트릭 서치를 이용할 수 있습니다. 예를 들어, 어떤 조건을 만족하는 최솟값을 구하는 최적화 문제가 있다고 해봅시다. 정답이 될 수 있는 값들이 연속적이어야 한다는 말은, 정답이 x라고 했을 때, x이상의 값들은 모두 조건을 만족해야 한다는 것을 의미합니다. 그래프로 나타내면 아래와 같습니다.

왼쪽의 그림은 어떤 조건을 만족하는(결정 문제에서 true를 리턴하는) 최댓값을 찾는 경우, 오른쪽의 그림은 어떤 조건을 만족하는 최솟값을 찾는 경우라고 할 수 있습니다. 당연하게도, 위의 빨간 수직선이 드문드문 나타난다면(결정문제에서 true를 나타내는 값들이 연속적이지 않은 경우) 파라메트릭 서치를 이용해서 답을 구할 수 없게 됩니다.

정리하자면

1) 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우

2) (최솟값을 구하는 경우) 최솟값이 x라면, x이상의 값에 대해서는 모두 조건을 만족

3) (최댓값을 구하는 경우) 최댓값이 x라면, x이하의 값에 대해서는 모두 조건을 만족

의 세 가지 조건을 충족한다면, 파라메트릭 서치를 이용해 문제를 풀 수 있습니다.

파라메트릭 서치 예제

2805 나무 자르기