Algorithm/이분탐색
리트코드 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,..
백준 2110 공유기설치 c++ // 매개변수탐색, 이분탐색 hard
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 의사코드 1. 첫번째 집을 선택하는게 최선인가? ㅇㅇ 귀류법 : 첫번째집을 선택안하는게 최선이라고 가정 -> ex) 1 2 5 에서 2부터 2개선택(2,5) 하는경우 간격은 3 / (1,5)선택하는 경우 간격이4 -> 모순 - > 따라서 첫번쨰 집을 선택하는게 최적해를 보장한다. 2. 가장 중요한점은 st, en이 v의 값이 아닌 집간 최소..
백준 1253 좋다 c++ // 이분탐색 발상, 주의점(자기자신예외처리)
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1. 의사코드 1 2 3 3 3 4 i j LB UB 에서 1. 해당수(a[i]+a[j])가 존재한다면, UB-LB로 그 갯수만큼 더해준다 2. 문제 : 1 2 3 3 3 1 2 인 경우 : 3은 앞의 (1,2) 에서도 좋은수에 카운트되고, 뒤의(1,2)에서도 카운트 된다 -> 해결 : vis[LB]를 만들고, 이미 좋은수로 체크된경우 pass 하도록 했다. 3. 문제 : 이분탐색 주의점 : idx 가 i, j와 같은경우 예..