Algorithm/이분탐색

백준 2295 세수의합 c++ // 이분탐색 발상

https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 1. 이진탐색 발상 nC2들의 합배열 : two a를 탐색(n^2) * 이진탐색(lgN) 부분합을 구한후, 이진탐색을 하라!!! 2.의사코드 a[i]+a[j]+a[l]=a[k] 인 k 의 최대값 찾기 two(a[i]+a[j])==a[k]-a[l]인 k의 최대값 찾기! 3. 전체코드 #include using namespace std; typedef ..

백준 18870 좌표압축 c++ // 이분탐색

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 1. 시행착오 답 : 해당원소보다 작은 원소의 갯수 upper_bound - lower_bound 하면 정답이 아니다... lower-begin 이 정답이다. 2. 전체코드 #include using namespace std; int n,m; vector v1,v2; set s; int main() { ios_base::sync_with_stdi..

백준 10816 숫자카드2 c++ // 이분탐색, upper_bound, lower_bound

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 1. upper_bound, lower_bound(begin, end, target) 이분탐색으로 target원소중 가장 우측, 좌측 인덱스 반환 2.전체코드 #include using namespace std; int n,m; vector v; int main() { /* * 이진탐색 -> 2^50 -> 시간초과 * 역발상 : target에서 start로 수렴..

백준 1920 수찾기 c++ // 이분탐색 stl

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 1. 이분탐색 stl binary_search(begin, end , target) 넣으면 target이 있으면1, 없으면0 리턴해줌 2. 전체코드 #include using namespace std; int n,m; vector v; int main() { cin.tie(0); cin >> n; for (int i = 0; i < n; ++i) {..