매개변수 탐색 (Parametric Search)

매개변수 탐색

매개변수 탐색이란 최적화문제를 결정문제로 바꿔서 푸는 방법이다.
이진탐색과 풀이 방식이 유사하며, 시간복잡도는 $log_2(N)$이다.

매개변수 탐색을 사용하는 경우

1. 특정 지점 이전에는 조건을 만족하지만 이후에는 조건을 만족하지 않는 경우 최댓값을 구할 때

2. 특정 지점 이전에는 조건을 만족하지 않지만 이후에는 조건을 만족하는 경우 최솟값을 구할 때

매개변수와 결정함수

매개변수 탐색을 구현하려면 매개변수와 결정함수를 정의해야 한다.

매개변수는 찾고자 하는 최솟값 또는 최댓값이 존재하는 구간의 값을 의미한다. 매개변수는 연속이어야한다.

결정함수는 조건의 만족여부를 판정하는 함수이다. 문제에 제시된 조건에 때라 계산한 다음에 true 또는 false를 반환하여 조건의 만족여부를 알려준다.
결정함수의 결과또한 매개변수에 대해서 연속이야하며, 주어진 구간에 대해서 한 지점에서만 조건의 만족여부가 바뀌어야 한다. 즉, 구간의 앞부분에서 만족하다가 뒷부분에서 만족하지 않거나 구간의 앞부분에서 만족하지 않다가 뒷부분에서 만족해야 한다.

매개변수 탐색의 구현 예시

백준의 2110번 문제를 예시로 들어서 매개변수 탐색의 구현을 알아보자. 문제의 자세한 내용은 다음 링크를 참고하자.

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

이 문제에서는 수직선위에 있는 N개의 집중에서 C개의 집에 공유기를 설치할 때 가장 인접한 두 공유기 사이의 거리의 최댓값을 구해야 한다.

이 문제에서 매개변수는 가장 인접한 두 공유기 사이의 거리가 된다. 공유기 사이의 최소거리가 작으면 조건을 만족하지만, 특정 값을 넘어가면 조건을 만족하지 못할 것이다. 이때 조건을 만족시키는 최댓값을 구하면 된다.

결정함수는 공유기 사이의 최소거리가 주어질 때 C개의 공유기를 설치할 수 있는지 여부를 판정하는 역할을 맡는다.

이렇게 생각할 때 소스코드는 다음과 같이 작성할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, C; // N:집의 수, C: 공유기의 수
int houses[200001]; // 집의 위치

// 결정 함수 : C개의 공유기를 설치할 수 있는지 판정
bool install(int minDist) {
	int APtoInstall = C - 1; 
	int dist = 0;
	for (int i = 2; i <= N; i++) {
		dist += houses[i] - houses[i - 1];
		if (dist >= minDist) {
			APtoInstall -= 1;
			if (APtoInstall == 0) {
				return true; // 공유기를 모두 설치할 수 있다면 true 반환
			}
			dist = 0;
		}
	}
	return false; // 모두 설치할 수 없다면 false 반환
}

// 매개변수 탐색을 수행하는 함수
int maxOfNearestDist() {
	int hi = houses[N] - houses[1] + 1;
	int lo = hi;
	for (int i = 2; i <= N; i++) {
		lo = min(lo, houses[i] - houses[i - 1]); 
	}
	lo -= 1; 
	while (lo + 1 < hi) { // 이분탐색을 통해서 매개변수의 최댓값을 찾는다
		int mid = (lo + hi) / 2;
		if (install(mid)) {
			lo = mid;
		}
		else {
			hi = mid;
		}
	}
	return lo; // 찾고자하는 최댓값은 lo가 가리키므로 이를 반환
}

int main(void) {
	scanf("%d %d", &N, &C);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &houses[i]);
	}

	sort(houses + 1, houses + N + 1); //집들을 오름차순으로 정렬
	
	printf("%d\n", maxOfNearestDist());

	return 0;
}

참고자료

https://m42-orion.tistory.com/70
https://movefast.tistory.com/311