[알고리즘] Parametric Search

이상현·2025년 2월 18일

알고리즘

목록 보기

6/15

파라매트릭 서치

Parametric Search 란 이분 탐색을 활용한 기술이다.

이분 탐색은 정렬된 값에서 특정 값의 위치를 빠르게 찾기 위한 알고리즘인데,

이것은 주어진 $x$ 값에 대해 조건을 만족하는지 검증하는 함수 $f(x)$ 를 만족하는 가장 크거나 작은 $x$ 값을 찾기 위한 기술이다.

$f(i)$ 가 $true$ 이면 $i$ 보다 큰 값은 모두 $true$ 일 것이므로 $i$ 보다 작은 부분만 탐색하면 되고,
$f(i)$ 가 $false$ 이면 $i$ 보다 작은 값은 모두 $false$ 일 것이므로 $i$ 보다 큰 부분만 탐색하면 된다는 개념에서 시작한다.

로직

0	1	2	3	4	5	6
X	X	X	X	O	O	O

f(x) 의 반환값이 위와 같을 경우 f(x) 를 만족하는 가장 작은 값을 찾기 위해 어떻게 작동하는지 보자.

초기 중앙값 $f(3) = false$ 이므로 탐색 범위를 우측 (4에서 6)으로 변경한다.
4와 6의 중앙값 $f(5) = true$ 이므로 탐색 범위를 좌측 (4에서 4)까지 좁힌다.
$f(4) = true$ 이므로 최적의 해는 4가 된다.

즉, $f(x) = true$ 인 최솟값 $x = 4$ 를 찾게 된다.
이 개념을 활용하면 문제에서 특정 조건을 만족하는 최적의 값을 빠르게 찾을 수 있다.

시간복잡도

$f(x)$ 의 시간복잡도를 $O(g(N))$ 라고 하면 이분 탐색의 시간복잡도는 $O(\log N)$ 이므로

최종 시간복잡도는 $O(g(N) \log N)$ 이 된다.

예를 들어 $f(x)$ 의 시간복잡도가 $O(N)$ 이라면 N = 200,000 까지 가능한 $O(NLogN)$ 이다.

코드

int parametricSearch() {
	int start = 1;
	int end = 200000;
	int answer = -1;
	
	while(start <= end) {
		int mid = (start + end) / 2;
        
		if (func(mid)) { // 반환값이 true 면 왼쪽 구역 탐색 (end = mid - 1)
			end = mid - 1;
			answer = mid;
		} else {
			start = mid + 1;
		}
	}
	return answer;
}

func 함수를 이진탐색 내부에서 호출하면서 x 의 최소값을 찾아서 반환하는 코드이다.
start 보다 end 가 작아지면 while 루프를 탈출하고 가장 최근에 true 를 반환했던 mid 값이 answer 에 담겨있으므로 answer 을 반환한다.

실습 - 백준

백준 2110 - 공유기 설치

문제를 보면 집의 좌표 $X_i$ 가 최대 10억이고, 집의 개수 $N$ 은 20만이다.
집의 좌표가 임의로 주어지기 때문에 직접 가능한지 해보는 수밖에 없다.

모든 집을 순회하며 설치 해보기 isValid() -> $O(N)$ = 200,000
이진 탐색을 사용하여 가능한 최대 거리 찾기 -> $O(LogX)$ -> $Xi$ 가 최대 10억이므로 약 30
30 * 200000 = 약 600만으로 시간복잡도가 괜찮다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int c = Integer.parseInt(line[1]);
        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(x);

        int start = 1;
        int end = 1_000_000_000;
        int ans = -1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (isValid(n, c, x, mid)) {
                ans = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        System.out.println(ans);
    }

    private static boolean isValid(int n, int c, int[] x, int dist) {
        int count = 1;
        int recent = x[0];
        for (int i = 1; i < n; i++) {
            if (x[i] - recent >= dist) {
                count++;
                recent = x[i];
            }
        }
        return count >= c;
    }
}