Algorithm/매개변수 탐색

[Algo] 공유기설치 c++ // 매개변수 탐색 hard

* 의사코드행동영역f(x) 정의시 최대, 최소를 쓰지마라. 우리는 이문제를 결정문제로 바꿔서 풀어야한다.간격을 고정하고 탐색하라. (x)로 고정.되는지를 구현하는게 사실 핵심이다. (go 함수)참인경우, st = mid 임에 주의 // en = mid 아님!go 함수 구현완탐하면서 간격    설치(cur갱신) , cnt+1설치된 공유기 갯수가 c 보다 큰지 return//설치간격이 x 일때, 공유기 c개 이상 설치 가능한지ll go(ll x) { ll cur = arr[0]; //현재 설치된 위치 ll cnt = 1; //공유기 설치갯수, 1st는 항상설치 for (int i = 1; i = c;}f(x) 정의, go 함수 구현 모두 빡센 문제였다.f(x)를 현재간격으로 "고정" 하고간격..

[Algo] 백준 예산 c++ // 매개변수 탐색

* 의사코드먼저 함수를 정의하라.0일때, 1일때 나눠서 st, en의 위치를 결정하라solve 함수를 작성하라.min을 이용해서, 둘중 적은것을 누적하고, 그게 예산이하인지 확인하면 되는듯?예외케이스 고려할 필요없는듯 하다.//배정예산 상한액이 x일때, 되는지ll go(ll x) { if (x > m) return 0; //상한액이 총예산을 넘어가는 경우 //모든 요청이 배정될수 있는경우 if (sum x) tmp += x; else tmp += arr[i]; } return tmp //by 바킹독bool solve(int uplim) { int sum = 0; for(int i = 0; i = sum;} * 전체코드solve 부분만 제외하면 바킹독님 코드와 ..

[Algo] 백준 랜선자르기 c++ // 매개변수 탐색

이 문제는 2회차푸는 문제다.x길이의 고정된길이로 막대를 자른다는 제약조건이 있다. (파악하기 힘들었음) * 매개변수 탐색 학습, 의사코드매개변수 탐색은 이분탐색의 응용편이다.f(x)를 정의하라. // f(x) : 랜선의 길이가 x일때, 갯수가 11개 이상이 나오는지.우선, f(1)과 f(끝)을 직접 구한다.랜선의 길이가 1일때, 갯수는 무조건 11개 이상이나온다.랜선의 길이가 max일때, 갯수는 무조건 1개이다.f(mid)가 참인경우같은숫자를 연결하면된다.즉, f(1) ~ f(mid)는 계산할필요없이 모두 1인것이다. 이경우, 우측으로 재귀적으로 재탐색하면 된다.이때, mid자체도 정답의 범위에( true이므로) 포함되기떄문에, st = mid로 둬야함에 주의f(mid)가 거짓인경우같은숫자를 연결하면된..

백준 2110 공유기설치 c++ // 매개변수탐색, 이분탐색 hard

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 의사코드 1. 첫번째 집을 선택하는게 최선인가? ㅇㅇ 귀류법 : 첫번째집을 선택안하는게 최선이라고 가정 -> ex) 1 2 5 에서 2부터 2개선택(2,5) 하는경우 간격은 3 / (1,5)선택하는 경우 간격이4 -> 모순 - > 따라서 첫번쨰 집을 선택하는게 최적해를 보장한다. 2. 가장 중요한점은 st, en이 v의 값이 아닌 집간 최소..

백준 2805 나무자르기 c++ // 이분탐색, 매개변수탐색, 정답후보를 for문 돌려라

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 의사코드 1. 적어도 n이상.. 문제 -> 결정문제로 바꿔서 푼다 2. 정답후보 : 0~20억에 대해 st, en으로 이분탐색 3. 이분탐색 공식은 암기토록 하자. 2. 전체코드 #include using namespace std; typedef long long ll; ll n,m, a[1000000 + 4]; //길이가 x일때, 가질나무가m개 이상인..