파라메트릭 서치(Parametric Search)

파라메트릭 서치(Parametric Search)

 

파라메트릭 서치란?

 

 - 문제를 최적화 하는 방법 중 하나.

 

 - 특정 값을 구하라는 문제(최대 값, 최소 값을 구하라)를 결정 문제로 바꿔서 생각하는 방법이다.

 

 - 특정 조건에 맞는 최대 값을 구하라 => 값 X가 특정 조건에 맞는가?

 

 - 이분 탐색을 이용하여 알맞는 X값을 찾는다.

탐색 알고리즘 - 이분 탐색(Binary Search)

 

 - 시간 복잡도 : O(MlogN)

    M : 값 X가 주어졌을 때 조건에 맞는지 확인 하는 시간 복잡도

    N : 값 X가 될 수 있는 최대 값.

 

---

 

파라메트릭 서치의 조건

 

 - 결정 문제로 바꾸고 생각하는 X가 연속된 값이어야 한다.

    (TTTT...TFF...FF / FFF...FFTT..TTT 와 같은 형태) 

 

 - EX) 돌다리가 주어졌을 때 건널 수 있는 사람의 최대 값을 구하라.

 

 

 

---

파레메트릭 서치 과정

 

 - 1. 정답이 될 수 있는 X의 범위를 설정한다.

 

 - 2. START에는 X의 최소값, LAST에는 X의 최대값을 설정한다.

 

 - 3. START와 LAST의 중간값인 MID를 결정한 후 MID가 정답이 될 수 있는지 판단한다.

 

 - 4. MID가 정답이 가능한지, 아닌지에 따라 START와 LAST의 범위를 줄여 2번 과정을 반복한다.

      이 과정에서 사용하는 것이 이분탐색이다.

 

 - 참고) 파라메트릭 서치 조건에 따라 X는 연속된 형태를 가지고 있기 때문에 이분탐색이 가능하다.

 

 - 아래 예제 그림은, 조건에 맞는 최대 값을 찾는 것이다.

 

 - 최대값이 3인 경우 0 ~ 3까지는 모두 조건을 만족하고, 4~14까지는 모두 조건을 만족하지 않는다.

MID인 7이 FALSE이기 때문에 7이상은 탐색할 필요가 없다.(모두 FALSE이다) LAST = MID-1이 된다.

MID인 3이 TRUE이기 때문에 3이하는 탐색할 필요가 없다(모두 TRUE이다) START = MID+1이 된다.

 

 

MID인 5가 FALSE이기 때문에 5이상은 탐색할 필요가 없다.(모두 FALSE이다) LAST = MID-1이 된다.

 

MID인 4가 FALSE이기 때문에 4이상은 탐색할 필요가 없다.(모두 FALSE이다) LAST = MID-1이 된다.

 

 

MID인 4가 FALSE이기 때문에 4이상은 탐색할 필요가 없다.(모두 FALSE이다) LAST = MID-1이 된다

 

 

START > LAST인 상황이 되었기 때문에 찾는 과정이 종료되고, 정답은 LAST가 된다.

 

 

 - 이 과정에 중요한 것은 모든 정답이 LAST가 되는 것이 아니라는 것이다.

   조건이 최소인지, 최대인지 등 상황에 따라 START가 되기도 하고 LAST가 되기도 하기 때문에 항상 주의해야 한다.

   결국은 정답은 한 번 이상 거치기 때문에 TRUE인 경우 최대, 최소를 갱신하는 것이 가장 좋다.

 

---

 

파라메트릭 서치 예시 코드

#include <bits/stdc++.h>

using namespace std;

int boards[100001];
int N, M;

bool func(int number) {
	int sum=0;
	int m = 1;
	for (int i = 0; i < N; i++) {
		sum += boards[i];
		if (number < boards[i]) {
			return false;
		}
		if (sum  > number) {

			sum = boards[i];
			m++;
		}
	}
	
	if (m > M) {
		return false;
	}
	return true;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int n;
		cin >> n;
		boards[i] = n;
	}

	int last = 1000000000;
	int start = 1;

	while (start <= last) {

		int mid = (start + last) / 2;

		bool result = func(mid);

		if (result) {
			last = mid-1;
		}
		else {
			start = mid + 1;
		}

	}
	cout << start << endl;



	return 0;
}

 

 

2343번: 기타 레슨

 

---

 

파라메트릭 서치 문제

 

 

2343번: 기타 레슨

 

 

2352번: 반도체 설계