Algorithm/이분탐색

프로그래머스 숫자게임 c++ // 이진탐색, 투포인터

https://school.programmers.co.kr/learn/courses/30/lessons/12987[프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/12987)처음접근이분탐색 && visit 이용upper_bound로 초과인 것 선택 -> 그것 제출문제 : A가 정렬이 아니기때문에 뒤의 작은숫자에대해 B가 점수를 얻는경우를 계산못함.반례 : A [ 2 2 1]B [ 1 2 3]3제출 , 1점2보다 큰 미방문 없음 -> break, 종료실제정답 : 2점#include using names..

[Algo] 백준 가장 긴 바이토닉 부분 수열 c++ // LIS, LDS, (dp), 이분탐색

* 시도완탐 : 해당 원소를 포함, 불포함 o, x로 나누어서 완탐하기2^1000 -> 불가완성된 배열에서도 바이토닉 찾기가 매우 까다로움dp -> n^2에 가능하나, n lgn풀이인 이분탐색으로 풀고자함.for (int i = 0; i lis의 len 구한후, 뒤집어서 범위제한후 len2 구하고 더하면 될듯?#include using namespace std;typedef long long ll;ll lis[1004], lis2[1004];ll nums[1004];int n,len, len2;int main(){ cin >> n; for (int i = 0; i > nums[i]; } int last_idx = 0; for (int i = 0; i  * 수정단순히 길이..

리트코드 153 회전 정렬 배열에서 최소값 찾기 c++ // 이분탐색

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/1. 의사코드우리는 보물인 0을 찾는것이다.[4 5 6 7 0 1 2]st      m       enmid>en이면, 보물이 우측에 있는것이다. -> st=mid+1[0 1 2]에서mid 0 en=mid; //mid-1아님[0 1]에서mid=0 보물이 좌측 -> en=0;en과 st가 0으로 수렴했고, 그곳이 보물이다! 2. 전체코드class Solution {public: int findMin(vector& nums) { int st=0,en=nums.size()-1; while(st

백준 14003 LIS 5 c++ // LIS 이분탐색 오류수정, LIS 출력하는법

https://www.acmicpc.net/problem/140031. LIS 오류수정이전문제는  Ai가 1부터시작하기 때문에if(lis[idx]==0) 이 해당 num이 처음등장하는 개큰수임 과 필요충분조건이 된다하지만, Ai에 0이 있는경우 이 '0'이 처음등장한다는 의미인지 lis안에 계산된 '0'이 라는 의미인지 불명확하다!!!// https://www.acmicpc.net/problem/14003 따라서, if(idx == len) 이렇게 하는것이 Ai의 범위에 상관없이 처음등장하는 개큰수라는 것과 필요충분조건이다!!//lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!! 예시) lis : -2 0 0 5에서 -1삽입시 lis[idx]==0이고, len+1이된다.하지만, len증..

백준 12015 LIS c++ // 이분탐색, LIS nlgn풀이 종결?, 한계

https://www.acmicpc.net/problem/12015 1. 설명1. 기존 dp : O(n^2) // n개입력에대해 * 앞의n개를 살펴보며 최대값을 찾아야함2. lower_bound : lb성질에 의해 n개입력 * lgn으로 구현쌉가능 2. 의사코드1. num을 1개씩보면서2. (lis에없는) 개큰수가 등장한경우, lis길이+13. 나머지는 lb성질에의해 날먹된다.작은값이오면, 기존값을 작은값으로 교체함 i)작은값이옴 -> 10 20 30 에서 25in, idx=30, 30값이 25로 교체됨ii)같은값이옴 -> 10 20 30 에서 20in, idx=20, 변화없음iii)개큰값이옴 -> 10 20 30 [ ]에서 40in , idx=0, lis에 추가해줌4. ex)10 -> 저장, lis+1..

백준 13423 ThreeDots c++ // 이분탐색

https://www.acmicpc.net/problem/13423 13423번: Three Dots 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,000)이 주어 www.acmicpc.net 1. 의사코드 1. 2중포문으로 nC2를 함 2. mid값이 존재한다면, 간격이같은 순서쌍이 존재하는것임 -> cnt+1 3. 단, 간격이 홀수이면 mid가 x.5가 되므로 반드시 불가능함 -> continue 처리 4. 시간복잡도 : nC2 (1000*1000/2) * log 1000(이분탐색) 2. 전체코드 #include typedef long long ll; usin..

프로그래머스 연속된부분수열의합 c++ // 정렬된 입력은 이분탐색, 누적합

https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 의사코드 0. 오름차순 정렬조건 -> 이분탐색은 정렬시에만 사용가능하다 -> 이분탐색을 이용해 보자! 1. 누적합배열을 만들고 2. 예외처리 : 누적합에 정답(k)가 있는경우 누적합 정의에따라 [0,해당idx]가 정답후보임 3. 누적합배열을 돌면서, k + v[i]가 존재한다면, [i+1, 찾은idx]가 정답후보임 // +임에 주의, 3 일경우 10을찾아야 10-3 == 7(k) 가 됨 4..

백준 7453 합이0인네정수 c++ // 이분탐색 갯수세기는 ub-lb

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 1. 의사코드 1. a+b의 결과를 답은 배열v1생성 2. c+d의 결과를 담은 배열 v2생성 3. v2에서 -v1을 이분탐색후 UB-LB == 해당순서쌍의갯수를 ret에 더해나감 2.시행착오 위의 3번과정에서 단순히 binary_search가 참이면 ret+1을 함 문제 : v1 : 2 , v2 : -2 -2 -2 일때, 순서쌍은(0,0,2,2) (0,0,2,3) (0,0,2,..