[Algorithm] 매개변수 탐색 (Parametric Search)

 

매개변수 탐색 (Parametric Search)

: 최적화 문제를 결정 문제로 바꾸어 푸는 것

 

❓ 최적화 문제: 가장 최선의 값을 도출해내야하는 문제. 최대, 최소의 값을 요구하는 문제들이 이에 해당한다.

❓ 결정 문제: 결과가 참/거짓으로 나오는 문제

 

매개변수 탐색은 이진 탐색의 연장선에 있는 알고리즘으로, 이진 탐색 알고리즘에 대한 이해가 선요구된다.

이진 탐색에 대해 알고싶다면?

 

 

기본 아이디어

 조건을 만족하는 수 가운데에서 최댓값을 찾기 위해서는 큰값부터, 최솟값을 찾기 위해서는 작은값부터 차근차근 선회하는 선형 탐색 알고리즘은 최적화 문제를 풀기에 가장 직관적으로 해결할 수 있는 알고리즘이다. 하지만 선형 탐색은 시간 복잡도가 O(n)으로 매우 비효율적이다.

 

그래서 등장한 것이 바로 매개변수 탐색 알고리즘인데, 

이진 탐색이 "target이 해당 배열에 존재하는가?" 에 대한 결정 문제였다면, 

매개변수 탐색은

"최댓값(최솟값)은 얼마인가?"라는 최적화 문제를

"범위내의 특정 값이 조건을 만족하는가?" 에 대한 결정 문제로 바꾼 후,

범위를 좁혀가며 조건을 만족하는 수를 찾되, 찾고 나서도 계속 탐색을 이어나가면서 최적의 답에 도달하도록 한다.

 

즉, 이진탐색은 target과 배열내 원소와의 (일치)에 집중하고,

매개변수 탐색은 배열내 원소가 (주어진 조건에 만족하는가)+(조건을 만족하는 더 나은 수가 있는가)에 집중한다.

 

 

메인 로직

1. 이진 탐색과 같이 low(배열의 최솟값), high(배열의 최댓값), mid(배열의 중앙값)를 설정한다.
2. mid의 값이 조건을 만족하는지 판별한다. 
    if 만족한다면: mid의 값을 별도로 저장해두고 조건을 만족하는 방향으로 범위를 좁힌다.
    else: 조건을 만족하는 방향으로 범위를 좁힌다.
    => (범위를 좁히는 방식) 최댓값 요구시: low = j+1, 최솟값 요구시: high=j-1
3. 위의 2.과정을 low>high가 되기 전까지 이를 반복하고 2.에서 최종적으로 별도로 저장한 값이 최적해가 된다.

 

 

예시코드(Python)

백준의 대표적인 매개변수 탐색 문제인 2805번 나무 자르기 문제의 내 답을 가져왔다.

import sys
MINIMUM = 1000000000

def opt_length(trees, needs):
    min_length = MINIMUM
    low = 0; high = max(trees)
    while low <= high:
        j = (low+high)//2; amount = 0
        for tree in trees:
            if tree-j > 0:
                amount += tree-j
        if amount >= needs:
            min_length = j
            low = j+1
            continue
        else:
            high = j-1
            continue
    return min_length
            
N, needs = map(int, sys.stdin.readline().split())
trees = list(map(int, sys.stdin.readline().split()))
result = opt_length(sorted(trees), needs)
print(result)

 

 

---

관련 백준 문제

• 1645 랜선 자르기

• 2805 나무 자르기