목록Algorithm/이분탐색 (23)
Mini
https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. db설정 : map m; 카카오 문제는 db설정을 잘해야한다. java back junior pizza 100 일때, 각각각 빈칸인경우와 빈칸아닌경우로 분기하면서 모든경우의 수에 대해(2^4) m[문자열] = { 100, ... } db를 완성한다. 2. 쿼리에서는 단순 조회만하면된다. m[javaback] = {1,2,3,4,4,5} 가있을떄, 4를 찾고있으면 end에서 4의위치(lower..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1. parametric search 최적화문제 -> 결정문제로 바꿔서 해결한다. 단, 감소또는 증가함수에서만 사용가능하다. 이경우에는 랜선길이up => 랜선갯수down 이다. ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ N개로만들수있는 랜선의 최대길이 -> 랜선길이가x일때, 랜선갯수가 N개이상인가? 2.의사코드 while (st < en) { ll mid = (st +..
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 ..
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..
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로 수렴..
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) {..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i www.acmicpc.net* 기본개념1. 목표가 100이고, 20이 현재값이면 visited[80]이 true -> 정답이 가능하다. * 에러out of bounds 원인 : visitied[x-v[i]]해결 : x가 최대 20만 이므로 visited도 20만으로 선언#include using namespace std;int n, x, visited[2000004], ret;vector v;int..