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

SungJun·2021년 4월 15일
5


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

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

파라메트릭 서치(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 이하의 값에 대해서는 모두 조건을 만족해야 한다는 내용인데 이분탐색을 사용하기 위해서 정렬된 상태의 데이터들을 활용하여 풀이하면 두 번째 조건도 만족할 수 있다.

추천문제

백준 2512번: 예산
백준 2805번: 나무 자르기
백준 2470번: 두 용액

🔎 참고자료

https://sarah950716.tistory.com/16 [주니어 개발자의 대나무숲]
도서 - 이것이 취업을 위한 코딩 테스트다 with 파이썬 (저자: 나동빈)

profile
기본기를 다지자

0개의 댓글