매개 변수 탐색(parametric search, 파라메트릭 서치)

매개 변수 탐색은 최적화 문제를 결정 문제로 바꾸어 풀 수 있게 해주는 기법이라고 한다.

최적화 문제란 말그대로 어떠한 함수값을 최적화시키는 변수를 찾는 문제,

그리고 결정 문제는 예-아니오의 형태로 답안이 나오는 문제를 말한다.

 

매개 변수 탐색의 기저는 이분 탐색인데,

이것을 결정 문제로 바꾼다고 해서 mid가 가리키는 값이 정답인지 바로 알 수 있는건 아니다.

다만 그 값이 정답이 될 수 있는지 정도는 바로 알 수 있다.

매개 변수 탐색은 그 결과를 이용해 탐색 범위를 좁혀가며 답을 찾는 기법이다. 마치 스무고개와도 같다.

 

문제를 통해 이해해보자.

아래 문제는 백준 단계별을 따라갔을 때 처음으로 만날 수 있는 매개 변수 탐색 문제이다.

 

https://www.acmicpc.net/problem/1654

 

문제에 대한 설명은 생략하겠다. 하지만 아래 풀이를 이해하기 위해선 문제를 읽어봐야 할 것이다.

 

내가 이 문제를 선택한 이유는 "N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다" 라는 설명이 있기 때문인데, 보통은 이런 설명이 없다.

하지만 매개 변수 탐색에 있어서는 굉장히 중요한 내용이다. 결정 문제로서 '예' 와 '아니오' 를 구분해야 하기 때문이다.

이 문제는 아주 친절하게도 정답의 기준을 제시해준 것이다. 이러한 내용이 없다면 스스로 결정해야 한다.

 

아무튼 바로 풀이 과정을 살펴보자.

 

 

우리는 제일 먼저 탐색의 범위를 정해야 한다.

사실 범위는 널널하게 잡아도 상관없다. 이분 탐색 자체가 워낙 빠르기 때문에 구체적인 범위를 정하는게 귀찮다면 대충 오버플로우가 일어나지 않는 선에서 때려넣어도 괜찮다.

하지만 나는 입력값 중에서 가장 큰 값인 802를 Right로 잡았고 1을 Left로 잡았다.

803 이상으로 자르는 것은 누가 봐도 불가능해 보였기 때문이다.

 

그래서 1과 802를 각각 Left, Right로 잡으면 Mid는 (1 + 802) // 2 = 401이 되는데,

여기서 우리가 알고 싶은 것은 이 Mid 값이 정답이 될 수 있는지이다. (정답인 지가 아니다)

 

입력으로 주어진 4개의 랜선들 [802, 743, 457, 539] 을 401의 길이로 잘라보자.

그러면 차례대로 2개, 1개, 1개, 1개의 랜선을 얻을 수 있으므로 총 7개의 랜선을 얻을 수 있는데, 이것은 N = 11개보다 작은 값이다. (참고로 몫 연산으로 구할 수 있다)

우리는 여기서 두 가지 사실을 알 수 있다.

 

첫 번째는 401은 정답이 될 수 없다는 것이고, (결정 문제)

두 번째는 401보다 큰 값도 정답이 될 수 없다는 것이다. (이분 탐색)

 

401보다 큰 값으로 잘라봐야 개수가 더 줄어들면 줄어들었지 늘어날 일은 없기 때문이다.

그래서 우리는 단 한번의 계산으로 절반에 대한 결정을 마칠 수 있었다.

남은 수에 대해서도 계속 진행해보자.

 

 

이제 401 이상의 값들은 더 이상 정답이 될 수 없으므로 Right는 Mid - 1인 400이 되었다.

그러면 Mid는 200인데, 예제에서 알 수 있다시피 정답은 이 200이다.

실제로 계산해보면 200만큼 잘랐을 때는 11개가 나오지만 201만큼 잘랐을 때는 10개가 나온다.

 

그래서 이번에 알 수 있는 사실은 200 이하의 숫자들은 정답이 될 수도 있다는 것이다.

(아직 정답으로 확정된 것이 아니다)

 

위에서 강조했지만 N개보다 많이 만드는 것도 N개를 만드는 것에 포함되기 때문이다.
무슨 말인지 이해하기 어렵다면 그냥 N개보다 많이 만들고 남은건 버려도 된다고 생각하자.

 

따라서 200 이하의 숫자들은 계산할 필요가 없으므로 Left는 Mid + 1인 201이 된다.

그러면 Mid는 300이 되고, 또 Right가 움직여서 Mid는 250이 되고, 225가 되고, 212가 되고...

결과적으론 이런 모습이 된다.

 

이해를 돕기 위해 색을 칠해봤다.

초록색으로 칠한 부분은 정답이 될 수 있는 부분이고, 빨간색으로 칠한 부분은 정답이 될 수 없는 부분이다.

이제 남은 숫자는 201과 202밖에 없는데, 아까도 말했지만 201로 계산해보면 개수는 10개가 나온다.

따라서 정답이 될 수 없고 개수를 늘리기 위해 Right는 Mid - 1인 200으로 이동한다.

 

그렇게 Right가 200으로 이동하면서 탐색은 종료되었다.

이분 탐색의 조건인 Left <= Right에 위배되었기 때문이다.

여기서 우리가 구하고자 하는 것은 정답의 최댓값이므로, Right를 취하면 예제의 정답인 200을 얻을 수 있다.

 

이렇듯 매개 변수 탐색은 결정 문제와 이분 탐색을 결합하여 불필요한 계산을 건너뛰게 해주는 기법이다.

"이 값이 최적의 값인가 / 이 값이 정답인가" 라는 어려운 문제를 "이 값이 정답이 될 수 있는가" 라는 비교적 쉬운 문제로 바꾸어 품으로써 마치 스무고개를 하듯 가볍게 문제를 해결할 수 있었다.

 

완전 탐색이었다면 시간 복잡도가 O(n)이었을 것을 무려 O(log n)만에 해결하게 해주니 정말 사랑스러운 알고리즘이 아닐 수 없다.