Algorithm/이분탐색

백준 14921 용액합성하기 c++ // 이분탐색 정석패턴

https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 1.의사코드 1. v[i]를 돌면서 -v[i]의 idx를찾는다 2. 정답후보는 idx-1, idx, idx+1이다. 3. 범위쳌 / 자기자신제외 / 정답갱신 2. 전체코드 #include using namespace std; typedef long long ll; ll ret=200000000+1; int n; vector v; int main() { ios::sync..

백준 2473 세용액 c++ // 이진탐색 패턴정석 외우기

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 1. 의사코드 -97 -6 -2 6 98 103 104 i j LB(idx) 에서 1. 정답후보는 idx-1, idx, idx+1이고, //사실 idx+-2도 탐색을 해야 한다! 2. 조건 : 범위내 && idx가 i또는 j와 달라야되고 && 현재정답보다 최적해여야한다. 2. 내코드 #include using namespace std; typedef long long ll; ..

백준 3151 합이0 c++ // 이분탐색, nC3최적화하는법

https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 1. 의사코드 1. 이진탐색범위 : j+1부터 탐색한다 2. UpperBbound-LowerBbound가 합이3인사람의 숫자이다. //중복없는 ※ 3이 없는경우 ub==lb가 되어 0명이다. 2.전체코드 #include using namespace std; typedef long long ll; ll ret; int n; vector v; set s; int vis[10004]; int main() {..

백준 2467 두용액 c++ //이분탐색 정답후보를 탐색하라

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 0. 시간복잡도 10만*10만 -> 시간초과 -> 10만*이분탐색(log10만) -> 쌉가능 1. 의사코드 -99 -2 -1 4 98 99 100 1. lowerbound로 99를 찾는다. 2. lower_bound 특징(99이상인 위치 리턴) 으로 인해 정답후보는 98 or 99 or 100 중 하나이다. 3. 조건 : 범위내 and 현재정답보다최적 and 자기자신은제외 4. 자기자신제외 ..

백준 18869 멀티버스2 c++ // 값을 idx로 바꿔라, 이분탐색이용, unique사용법

https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 1. 의사코드 1. 숫자 -> 크기순 idx로 변환한다 ex : 10 20 30 -> 0 1 2 ex2: 1 2 3-> 0 1 2 2. 변환후 같은배열이면, 같은우주이다. 2. 구현 1. v에 arr복사, 고유값만 남기기 2. v를 이분탐색하며 arr을 arr(idx)로 교체하기 3. 전체코드 #include using namespace std; int m, n,ret,arr[104][10..

백준 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개 이상인..

프로그래머스 순위검색 c++ // 이분탐색, db설정

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..

백준 1654 랜선자르기 c++ // 이분탐색, parametric search

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 +..