algospot :: DARPA DARPA Grand Challenge

문제 : https://algospot.com/judge/problem/read/DARPA

알고리즘 문제 해결 전략 p. 449

(동적 계획법으로도 풀 수 있다고 나와 있지만) 최적화문제를 결정문제(yes/no 로 답이 나오는 문제)로 바꿔서 푸는 유형의 문제이다.

[최적화 문제를 결정문제로 바꾸는 방법]

1. "가장 좋은 답이 무엇인가?" -> "x 또는 그보다 좋은 값이 있는가?"라는 결정문제 형태로 바꿈.

2. 결정 문제를 쉽게 풀 수 있는 방법이 있는지 찾아봄.

3. 결정문제를 내부적으로 이용하는 이분법 알고리즘을 작성.

[이분법의 함정]

어떤 문제의 정답이 4.2라고 가정하자. 그런데 연산 중 수치적 오차가 생겨서 4.2에 대해 참 또는 거짓을 반환했다고 하자. 그러면 optimize()는 4.2를 상한으로 하고 4.2와 가까운 숫자들을 계속 시도하다가 4.199999... 를 반환한다. 이는 수치적 오차가 생겨도 답이 크게 달라지지 않으므로 문제가 없다.

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

[알고리즘 STEP. 1]

원래의 문제 "가장 가까운 두 카메라 사이 간격을 최대화 했을 때 간격은 무엇인가?" 를

 "x또는 그보다 두 카메라 사이 간격이 최대화 되는 값이 있는가?" 의 결정문제 형태로 바꾼 후에 문제를 푼다.

* double optimize(const vector<double>& locations, int cameras)

최적화 문제를 결정문제로 넘겨주고, 최적값을 찾는 함수이다. 

"x또는 그보다 두 카메라 사이 간격이 최대화 되는 값이 있는가?"  를 decision(x)라고 해보자.

지금 x가 존재할 수 있는 총 범위가 0<= x <200이라고 하면, 이 범위의 중앙값 x = 100에 대해서 결정문제를 풀어보고,

결정문제의 답을 활용해서 x가 존재할 수 있는 값의 범위를 줄여가면서 최적 값을 찾는다.

예를들어, 최적화 했을 때의 x = 80이라면

다음과 같이 x가 있을 수 있는 숫자의 범위를 줄여나가면서 x값을 찾을 수 있다.

decision(100) : FALSE   . . .  0<= x < 100 decision(50) : TRUE      . . .  50<= x < 100 decision(75) : TRUE       . . .  75<= x < 100 decision(87.5) : FALSE  . . .  75 <= x < 87.5 . . .

이에 대한 코드는 다음과 같다.

각 위치는 240 이하의 실수라고 했으므로 high를 그보다 1 큰 값인 241로 잡는다.

그 후에 decision(low) && !dicision(high) 가 되는 조건을 찾아서 반복적으로 결정문제를 풀어보고, 마지막에 low의 값을 반환한다.

double optimize(const vector<double>& locations, int cameras){ double low = 0, high = 241; // *** decision(low) && !dicision(high)가 될 때 까지!!!! FOR(i, 100){ double mid = (low+high)/2.0; //간격이 mid이상 되도록 할 수 있으면 답은 [mid, high]에 있다 if(decision(locations, cameras, mid)) low = mid; //간격이 mid이상 되도록 할 수 없으면 답은 [low, mid]에 있다 else high = mid; } return low; }

*bool decision(const vector<double>& locations, int cameras, double max)

변환된 결정문제 부분의 함수이다.

마지막으로 확인한 [카메라를 설치할 수 있는 위치] + max 보다 멀리 떨어진 최초의  [카메라를 설치할 수 있는 위치] 에 카메라를 설치한다.

원하는 만큼의 카메라를 다 설치했으면, max의 gap을 두고 카메라 cameras개를 설치할 수 있다는 뜻이므로 true를 반환한다.

bool decision(const vector<double>& locations, int cameras, double max){ double current = -1; FOR(i, locations.size()){ if(current <= locations[i]){ cameras --; current = locations[i]+max; } if(cameras == 0) return true; } return false; }

[최종코드]

#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #define FOR(var, ed) for(int var = 0 ; var < ed; var++) using namespace std; int tc, n, m; vector<double> locations; void input(){ cin >> n >> m; locations.clear(); locations.resize(m); FOR(i, m) cin >> locations[i]; } bool decision(const vector<double>& locations, int cameras, double max){ double current = -1; FOR(i, locations.size()){ if(current <= locations[i]){ cameras --; current = locations[i]+max; } if(cameras == 0) return true; } return false; } double optimize(const vector<double>& locations, int cameras){ double low = 0, high = 241; // *** decision(low) && !dicision(high)가 될 때 까지!!!! FOR(i, 100){ double mid = (low+high)/2.0; //간격이 mid이상 되도록 할 수 있으면 답은 [mid, high]에 있다 if(decision(locations, cameras, mid)) low = mid; //간격이 mid이상 되도록 할 수 없으면 답은 [low, mid]에 있다 else high = mid; } return low; } int main(){ cin >> tc; while(tc--){ input(); sort(locations.begin(), locations.end()); cout << fixed << setprecision(2); cout << optimize(locations, n) << endl; } }

[내가 헤맨 부분]

- 소수점 2째자리까지 출력 cout.precision(2)할 때는 안되고, cout << fixed << setprecision(2); 하니깐 됐음...

- optimize 함수는 범위를 줄여나가는 함수이다. decision(low) && !dicision(high)가 될 때 까지!!!!