개인공부용123 프로그래밍 블로그

문제 : https://algospot.com/judge/problem/read/CANADATRIP N개의 도시가 있는데 도시 M[i]미터 전부터 표지판이 세워지고 G[i]미터 간격으로 표지판이 세워진다. 이때 K번째 표지판의 위치를 구하는 문제이다. 이 문제또한 결정문제로 바꿔서 풀경우 빠르게 풀수 있습니다. 이분법을 이용해서 K개 이상의 표지판을 포함하는 거리를 좁혀나가면서 K개의 표지판을 포함하는 거리를 찾았습니다. #include #include #include using namespace std; int N, K; int L[5000], M[5000], G[5000]; // 시작점부터 도시의 거리, (표지판이)몇미터부터, (표지판이)몇미터 간격 bool decision(int dist) { in..

문제 : https://algospot.com/judge/problem/read/ARCTIC 동일한 성능을 가진 무전기로 모든 기지에 연락할떄 무전기 성능을 최소화하는 문제입니다. 이분법과 프림알고리즘 두가지 방법을 이용해서 풀었습니다. 두 기지사이의 거리정보를 미리 계산해서 배열에 넣은후 이분법에서는 queue를 이용해서 인자로 넣어진값으로 모든 기지에 연락할수있으면 true를 반환하고 아닐시 false를 반환하면서 점점 최적값으로 맞춰갔고프림알고리즘은 priority_queue를 이용해서 값을 계산했습니다. 100번 반복문을 실행하는이유는 절대오차가 10^-7보다 작게하기위해서입니다. #include #include #include #include #include #include #include us..

문제 : https://algospot.com/judge/problem/read/DARPA 카메라를 설치할때 가장 가까운 두카메라의 간격을 최대화 하는 문제입니다. 이분법과 그리디알고리즘을 이용해서 풀었습니다. 100번 반복문을 실행하는이유는 절대오차가 10^-7보다 작게하기위해서입니다. #include #include #include using namespace std; int N, M; // 카메라수 중계소수 vector loc; bool decision(double gap) { int install = 0; double min_limit = -1; for (int i = 0; i < loc.size(); ++i) { if (min_limit = N; } double optimize() { doubl..