[Algorithm] 이진탐색? 파라메트릭 서치?🤔

이진탐색과 파라메트릭 서치의 차이점에 대해 알아보자😊

처음에는 이진탐색과 파라메트릭 서치가 다른 종류의 알고리즘 인 줄 알았다 ㅎㅎ
근데 파라메트릭 서치는 이진탐색의 한 종류이고, 이진탐색의 유형을 활용해서 파라메트릭 서치 유형의 문제를 풀 수 있다!

조금 더 자세히 알아보자 😎

이진 탐색이란,

이진 탐색은 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘이다.
중간값을 선택하여 그 값과 찾으려는 값을 비교하면서 클 경우 선택했던 중간값을 최솟값으로, 작을 경우 중간값을 최댓값으로 하여 원하는 값을 찾을 때까지 이 과정을 반복하여 문제를 해결하는 방식이다.

한 과정을 거칠 때마다 탐색하는 범위가 절반씩 줄어드므로 시간 복잡도는 O(log N) 으로 빠른 속도의 탐색 알고리즘이다.
대신 정렬된 값들이 아닐 경우 탐색을 할 수 없다는 단점을 가진다!

예를 들어 위처럼 1부터 9까지 수가 주어졌을 때 3을 찾아야 한다라는 문제가 있다고 가정해보자!
1. 중간값인 5가 3보다 큰지 작은지 검사한다.
2. 3 < 5 이므로 5부터 9까지는 배제하고 1부터 4까지 중에서 다시 중간값( (1+4)/2 = 2.5 -> 2)과 3을 비교한다.
3. 2 < 3 이므로 1부터 2까지는 배제하고 3부터 4까지 중에서 중간값( (3+4)/2 = 3.5 -> 3)과 3을 비교한다.
4. 일치하므로 탐색을 종료한다.

파라메트릭 서치란,

파라메트릭 서치는 이진탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘이다.

이진탐색은 1부터 9까지의 값에서 3을 찾아내는 것이라면,
파라메트릭 서치는 1부터 9까지의 범위내에서 3을 찾아내는 것이다.

주어진 범위이기 때문에 특정 상황을 최적화 시키는 문제를 풀 때 사용하면 좋다.
또한 파라메트릭 서치를 사용하면 최적화 문제를 결정 문제로 바꾸어 풀 수 있어서 문제 접근이 상당히 용이해진다!

쉽게 말해서, 특정 상황에서 최대/최소값과 같은 특정 값을 구하는 문제가(=최적화 문제), 그냥 그 특정 값이 어떠한 조건을 만족하는지만 확인하면 되는 문제(=결정문제) 로 바뀐다는 의미이다.

파라메트릭 서치를 활용한 대표적인 문제로는 백준 1654:랜선자르기 문제가 있다!

주어진 랜선의 길이를 보면 2^31-1 보다 작거나 같은 자연수로 약 20억이 넘기 때문에, 순차탐색으로 풀면 시간초과를 받는다.

방금 정리한 파라메트릭 서치 방법을 적용해보면 어떨까😎?

풀이는 간단하다.
적절한 길이를 찾을 때까지 랜선의 길이를 반복해서 조절하면 된다.
'현재 길이는 조건을 만족하는가?' 라는 질문에 '예', '아니요'로 확인해주면서
중간값을 조절하며 탐색범위를 좁혀서 해결하는 것이다.

from sys import stdin

K, N = map(int, stdin.readline().split())
lans = [int(stdin.readline()) for _ in range(K)]

start, end = 1, max(lans)
res = 0

while start <= end:
    mid = (start + end) // 2
    cnt = 0

    for l in lans:
        cnt += l // mid

    if cnt >= N:
        start = mid + 1
        res = mid
    else:
        end = mid - 1

print(res)

➡️ 실제 내 코드이다 ㅎ

마지막으로, 파라메트릭 서치를 사용할 수 있는 조건을 알아보자!

1. 특정 조건을 만족하는 최댓값/최솟값을 구하는 형식의 문제여야 한다.
혹은 이러한 형태로 변형이 가능해야 한다.

2. 최댓값을 구하는 문제의 경우 어떤 값이 조건을 만족하면 그 값보다 작은 값은 모두 조건을 만족해야 한다.(최솟값의 경우 그 값보다 큰 값은 모두 조건을 만족해야 한다.)
그래야 조건을 만족하는 경우 더 큰 값을, 만족하지 않는 경우 더 작은 값을 확인하면서 이분탐색을 통해 답을 구할 수 있다.

3. 답의 범위가 이산적이거나(e.g. 정수) 허용 오차 범위가 있어야 한다.
이분탐색으로는 연속적인 범위에서 정답에 한없이 가까워질 수는 있지만 완전히 정확한 값은 구할 수 없기 때문이다.

참고 자료1
참고 자료 2