알고리즘 문제 해결 전략 1 12장 최적화 문제

int n, k;
int c[1000], r[1000];
bool decision(double average) {
	vector<double> v;
	for (int i = 0; i < n; i++)
		v.push_back(average * c[i] - r[i]);
	sort(v.begin(), v.end());
	double sum = 0;
	for (int i = n - k; i < n; ++i)
		sum += v[i];
	return sum >= 0;
}

double optimize() {
	double lo = -1e-9, hi = 1;
	for (int iter = 0; iter < 100; iter++) {
		double mid = (lo + hi) / 2;
		if (decision(mid))
			hi = mid;
		else
			lo = mid;
	}
	return hi;
}

12. 최적화 문제 결정 문제로 바꿔 풀기

12.1 도입

최적화 문제를 결정 문제로 바꾼 뒤, 이것을 이분법을 이용해 해결하는 방법이 있음. 결정 문제란 예 혹은 아니오 형태의 답만이 나오는 문제들을 가리킴. 

optimizae(G) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환함. 

desicition(G, x) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오면서 길이가 x이하인 경로의 존재 여부를 반환함

 

최적화 문제와 결정 문제의 관계
결정 문제가 최적화 문제보다 어려울 수 없음. 

 

예제: DARPA Grand Challenge

optimize(locations, cameras)=카메라를 설치할 수 있는 위치 locations와 카메라의 수 camears가 주어질 때, 카메라 간 최소 간격의 최대치를 반환. 이 문제를 결정 문제로 변환하면 어떻게 될까요?
decision(locations, cameras, gap)=카메라를 설치할 수 있는 위치 locations와 카메라의 수 cameras가 주어질 때, 이들을 적절히 배치해 모든 카메라의 간격이 gap 이상이 되도록 하는 방법이 있는가?

이와 같은 과정을 거쳐 답이 존재하는 범위를 계속 절반으로 줄여가다 보면 답이 있는 위치를 거의 정확하게 찾을 수 있음. 

 

결정 문제 풀기

이렇게 최적화 문제를 결정 문제로 변형하는 것은 좀 더 쉽고 빠른 방법이 있기를 기대하기 때문. 

bool decision(const vector<double>& location, int cameras, double gap) {
	double limit = -1;
	int installed = 0;
	for (int i = 0; i < location.size(); i++) {
		if (limit <= location[i])
			++installed;
		limit = location[i] + gap;
	}
	return installed >= cameras;
}

double optimize(const vector<double>& location, int cameras) {
	double lo = 0, hi = 241;
	for (int it = 0; it < 100; it++) {
		double mid = (lo + hi) / 2.0;
		if (decision(location, cameras, mid))
			lo = mid;
		else
			hi = mid;
	}
	return lo;
}

고정된 수의 후보만을 탐색하는 이분법에서는 이와 같은 오류가 생길 경우 4.2보다 작은 후부로 반환 값이 바뀌기 때문에 오차가 커질 수 있으므로 유의해야 함.

 

12.1 문제: 남극 기지

모든 무전기의 통신 반경은 d이며, 두 탐사 기지는 사이의 거리가 d이하여야만 서로 연락을 할 수 있음. 각 기지 간에는 다른 기지를 통해 간접적으로 연락할 수도 있지만, 항상 모든 기지 간에 서로 연락을 할 수 있어야 함. 가능한 한 무전기의 통신 반경을 최소화하고 싶음. 각 기지의 위치가 주어질 때, 가능한 한 무전기의 최소 통신 반경을 계산하는 프로그램을 작성하시오. 

 

12.3 풀이: 남극 기지

연락망이 주어질 떄, 무전기 통신 반경은 직접 연결된 두 기지 간의 최대 거리가 됨. 

optimize(P)=P에 주어진 기지들을 모두 연결하는 연락망을 구축할 때 가능한 최소 무전기 반경은 얼마인가?

decision(P, d)=모든 기지를 하나로 연결하되, 가장 먼 두 기지 간의 거리가 d이하인 연락망이 있는가?

서로 거리가 d 이하인 기지들을 우선 전부 연결해 연락망을 만든 뒤, 이들이 하나로 연결되어 있는지를 확인하면 됨. 결정 문제를 해결하고 나면 이분법을 이용해 원래의 최적화 문제도 해결할 수 있음.

int n;
double dist[101][101];
bool decision(double d) {
	vector<bool> visited(n, false);
	visited[0] = true;
	queue<int> q;
	q.push(0);
	int seen = 0;
	while (!q.empty()) {
		int here = q.front();
		q.pop();
		++seen;
		for(int there =0; there <n ;++there)
			if (!visited[there] && dist[here][there] <= d) {
				visited[there] = true;
				q.push(there);
		}
	}
	return seen == n;
}

double optimize() {
	double lo = -0, hi = 1416.00;
	for (int it = 0; it < 100; it++) {
		double mid = (lo + hi) / 2;
		if (decision(mid))
			hi = mid;
		else
			lo = mid;
	}
	return hi;
}

optimize()은 이분법을 이용해 decision()이 참을 반환하는 최소의 답을 찾아냄. 너비 우선 탐색의 시간 복잡도는 O(V+E)이고, 이 문제에서 E=O(n^2)이므로 decisionArctic()의 시간 복잡도는 O(n^2)입니다. 

 

12.4 문제: 캐나다 여행

시작점으로부터 각 도시까지의 거리 L와 M, G가 주어질 때, 동건이가 시작점으로부터 여행하면서 보게 되는 K번째 표지판의 위치를 계산하는 프로그램을 작성하시오. 한 위치에 표지판이 여러 개 있을 경우에도 각각의 표지판을 따로 세기로 함. 각 테스트 케이스마다 한 줄에 K번째 표지판의 위치를 출력합니다. 

 

12.5 풀이: 캐나다 여행

K번째 표지판의 위치는 어디인가라는 문제를 다음과 같이 바꿔봅니다. 

decision(x) = 시작점부터 x미터 지점까지 가면서 K개 이상의 표지판을 만날 수 있는가?

decision(D-1)=false, decision(D)=true여야 한다는 뜻임. 이와 같은 지점을 찾는 것은 이분법으로 간단하게 구현할 수 있음. 

int n, k;
int l[5000], m[5000], g[5000];
bool decision(int dist) {
	int ret = 0;
	for (int i = 0; i < n; i++)
		if (dist >= l[i] - m[i])
			ret += (min(dist, l[i]) - (l[i] - m[i])) / g[i] + 1;
	return ret >= k;
}

int optimize1() {
	int lo = -1, hi = 8030001;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		if (decision(mid))
			hi = mid;
		else
			lo = mid;
	}
	return hi;
}

 

12.6 수강 철회

어떤 학생이 듣는 i번째 과목의 수강생 수가 c라고 합시다. 백준이의 누적 등수를 계산할 수 있음. 수강 철회를 하면 철회한 과목은 중간 고사의 누적 등수 계산에 들어가지 않게 됨. 

 

12.7 풀이: 수강 철회

r/c가 큰 것부터 철회하기, r-c가 큰 것부터 철회하기 등의  전략을 써 봐도 답이 나오지 않음을 알 수 있음. 결정법으로 바꾸어 "누적 등수를 x이하로 하는 것이 가능한가?라는 질문도 대답하기 어려움. 

decision(x) = 적절히 과목들을 철회해 누적 등수 x 이하가 될 수 있을까?

부등호 좌변의 분모를 오르쪽으로 넘기고 적절히 정리하면 다음 식을 얻을 수 있음. x*c - r= v라고 함. 실수의 배열 v가 주어질 때, 이 주 k개 이상을 선택해서 그 합을 0 이상으로 만들 수 있는가 하는 문제로 바뀜. 이것은 v를 정렬하고 가장 큰 k개의 원소를 더해서 쉽게 풀 수 있음.