목록Algorithm/이분탐색 (23)
Mini
[틀림] 백준 2565 전깃줄 // 조합연속합, 이게 왜 LIS
https://www.acmicpc.net/problem/2565* 풀이완탐?조합으로 뽑아서 되는지 검사하면?조합연속합 공식 (완탐)100C1 + 100C2 + ... + 100C100 = 2^100 -1 -> 불가혹시 LIS?#includeusing namespace std; typedef long long ll;int n;int lis[104],len;vector> v;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=0;i>a>>b; v.push_back({a,b}); } sort(v.begin(),v.end()); for(int i=0;i
[틀림] 백준 LIS 5 // 원복 LIS
https://www.acmicpc.net/problem/14003* 풀이각 숫자에 대해ans[ ] 에 {idx, num}을 저장 해 놓는게 키포인트이후 뒤부터 탐색pos=len-1일때 stack에 넣기스택에 넣고빼면 역순출력 완성헤맸던 부분lower_bound 대상은 lis임. a가 아님lower_bound 범위는 (lis, lis+len임). lis + n이 아님초기화는 max+1로 초기화 (역시 lis가 대상. a 가 아님)#includeusing namespace std; typedef long long ll;int len, n;ll a[1000000+4];ll lis[1000000+4];pair ans[1000000+4]; // pos,numint main(){ ios_base::sync_w..
프로그래머스 숫자게임 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 * 수정단순히 길이..
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..
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..