파라메트릭 탐색(Parametric search)

[파라메트릭 탐색이란]

파라메트릭 탐색은 최적의 해를 탐색하는 문제를 yes/no의 결정 문제들로 나눠서 해결하는 탐색 방법이다.

 

사고 싶은 물건이 있을 때 내가 가진 예산 내에서 살 수 있는 가장 비싼 제품을 고르는 것과 같은 문제가 파라메트릭 탐색을 적용하여 해결한 수 있는 문제이다.

 

단 파라메트릭 탐색을 위한 전제 조건은 데이터가 정렬되어 있어야 한다는 것이다.

 

내가 사고자 하는 제품 단가들이 다음과 같이 주어진다고 하자.

goods_prices = [15, 17, 22, 26, 28, 30]

 

현재 예산은 27원이라 할 때 구매할 수 있는 가장 비싼 제품은 26원이다.

 

이 과정을 파라메트릭 탐색을 통해 진행해보자.

1. 먼저 탐색 전에 양 끝의 인덱스를 left, right로 설정한다.
2. 중앙 인덱스 mid = left + (right - left) // 2에 해당하는 금액과 예산을 비교한다. mid = 2이고 goods_prices[mid] = 22이다. 22 < 27 이므로 22는 예산으로 구매가 가능한 금액이다. 따라서 일단 우리가 찾는 해라고 간주한다.
3. 22원보다 큰 금액 중 최적의 해가 있는지 찾아야 하므로 left = mid + 1로 변경하여 2번 과정을 반복한다. mid = 4 이고 goods_prices[mid] = 28이다. 28은 예산을 벗어난 값으로 그 이후의 값들은 더 이상 신경 쓰지 않아도 된다.
4. 28원보다 낮은 금액 중 최적의 해가 있는지 확인해야 하므로 right = mid - 1로 변경하여 2번 과정을 반복한다. mid = 3이고 goods_prices[mid] = 26이다. 26원은 예산으로 구매할 수 있는 금액이므로 찾는 해를 26으로 변경한다.
5. left = mid + 1로 변경하면, left = 4, right = 3이 로 양 방향의 인덱스가 교차하게 된다. 이는 더 이상 탐색할 데이터가 없음을 뜻하므로 탐색을 종료하고 마지막으로 탐색했던 값 26이 우리가 찾고자 하는 해가 된다.

 

---

 

[파라메트릭 탐색 예제]

백준 2805번: 나무 자르기 (https://www.acmicpc.net/problem/2805)

 

 

import sys
from collections import Counter


n, m = map(int, sys.stdin.readline().split())
woods = Counter(map(int, sys.stdin.read().split())).items()
s, e = 0, max(woods)[0]
answer = 0
while s <= e:
    mid = s + (e - s) // 2
    if sum([(wood - mid) * c if wood > mid else 0 for wood, c in woods]) >= m:
        answer = mid
        s = mid + 1
    else:
        e = mid - 1
print(answer)