[이분탐색] 파라메트릭 서치(Parametric Search)

SungJun·2021년 4월 15일

이분 탐색 알고리즘의 개념을 학습하고 나면 한가지 궁금증이 생긴다. 이분 탐색 알고리즘이 어떤 식으로 문제에 출제될 수 있을까? 순차 탐색보다 더 빠르게 데이터를 탐색할 수 있어서 사용되는 것이 다일까?

이러한 궁금증을 가진 상태로 백준이나 코딩테스트를 통해 문제를 풀다 보면 전형적인 이분탐색 기법을 활용하여 풀 수 있는 문제들을 마주하게 되는데 바로 파라메트릭 서치 유형의 문제이다.

파라메트릭 서치(Parametric Search)란?

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

예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이분 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.

위 표현이 지금은 와 닿지 않을 수 있다. 전형적인 예제를 풀어보면 더 이해가 쉬울 것이다.

문제

백준 1654번: 랜선 자르기

풀이

순차 탐색으로 풀면 안 되는 이유

랜선의 길이는 2^31-1보다 작거나 같은 자연수로 20억이 넘는 수가 되는데 이 문제에서 랜선의 길이를 1부터 차례대로 증가시키며 푸는 순차탐색 방식으로 풀면 분명 시간초과를 받을 것임을 알 수 있다 이처럼 큰 수를 보면 이분 탐색을 떠올리도록 하자.
랜선의 길이를 이분 탐색으로 찾는다면, 대략 31번만에 경우의 수를 모두 고려할 수 있다. 이때 이미 가지고 있는 랜선의 개수 K가 최대 10,000이므로 랜선의 길이를 바꿀 때마다 만들 수 있는 랜선의 개수를 체크하는 경우 대략 3만 번 정도의 연산으로 문제를 풀 수 있다.

이분 탐색을 활용한 풀이

풀이 아이디어는 적절한 길이를 찾을 때까지 랜선의 길이를 반복해서 조절하는 것이다. 그래서 '현재 이 길이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부('예' 혹은 '아니오')에 따라서 탐색 범위를 좁혀서 해결할 수 있다.
범위를 좁힐 때는 이분 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀나간다.

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
data = [int(input()) for _ in range(k)]

left, right = 1, max(data)  
result = 0
while left <= right:
    mid = (left + right) // 2
    total = 0
    for i in data:
        total += i // mid

    if total >= n:
        left = mid + 1
        result = mid
    else:
        right = mid - 1

print(result)

정리

알고리즘적인 관점에서 이 문제가 파라메트릭 서치 유형의 문제인 근거는 파라메트릭 서치를 사용하기 위한 조건들을 모두 만족하기 때문이다.

1) 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우
2) 가능한 해의 영역이 연속적이어야 한다.

기존의 문제에 비해 시간복잡도가 낮은 다항 시간 알고리즘으로 이 문제의 경우 O(logN)로, 결정한 답 X에 대해 해를 만족하는지 확인할 수 있다.
(최솟값을 구하는 경우) 최솟값이 x라면, x 이상의 값에 대해서는 모두 조건을 만족해야 하고, (최댓값을 구하는 경우) 최댓값이 x라면, x 이하의 값에 대해서는 모두 조건을 만족해야 한다는 내용인데 이분탐색을 사용하기 위해서 정렬된 상태의 데이터들을 활용하여 풀이하면 두 번째 조건도 만족할 수 있다.