파라메트릭 서치 (Parametric Search) 22.6.6

사용자가 특정 차트를 고르면, 전 종목의 과거(10년) 차트들을 모두 탐색하여 가장 유사한 차트 10개를 골라 사용자에게 보여줍니다.

 

웹프로젝트 링크

비슷한 차트 검색기

 

 

 

파라메트릭 서치란

 

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

• 최적화 문제 : 상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제
• 결정 문제 : Yes, No 중 하나로 답할 수 있는 문제

문제를 풀어나가는 과정이 바이너리 서치(이분 탐색)와 매우 흡사하다. 파라메트릭 서치는 의외의 문제들에 적용돼서 최적화 문제들을 조금 더 쉽게 풀 수 있게 해 준다.

 

파라메트릭 서치의 핵심은 결정 문제다. 해당값이 정답이 될 수 있는 값인지 아닌지를 쉽게 판단할 수 있어야(즉, 결정 문제를 쉽게 풀 수 있어야) 최적화 문제를 파라메트릭 서치로 풀 수 있다. 또한, 정답이 될 수 있는 값들이 연속적이어야 파라메트릭 서치를 이용할 수 있다.

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

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

 

 

 

 

 

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

2343번: 기타 레슨

 

 

 

 

백준 2343 문제

 

파라메트릭 서치를 사용하여 풀 수 있다.

N, M = map(int, input().split())
lessons = list(map(int, input().split()))

def f(n):
    sum = 0
    cnt = 1
    for lesson in lessons:
        if sum + lesson <= n:
            sum += lesson
        else:
            cnt += 1
            sum = lesson        
    return cnt

lo = max(lessons)
hi = sum(lessons)
mid = (lo + hi) // 2
ans = 0
while lo <= hi: 
    if f(mid) <= M: # 최솟값을 구하니 <=, f(mid)가 작다는건 블루레이 크기가 크다는것 
        ans = mid # 이분 탐색과 흡사하다
        hi = mid - 1
    else:
        lo = mid + 1
    mid = (lo + hi) // 2
print(ans)