이분탐색

[프로그래머스] level2 순위 검색 (Python)

입력이 50,000이고, 쿼리가 100,000이다. 쿼리가 10만이라서 쿼리에 대한 답은 log 시간복잡도가 필요할거라고 감을 잡았다. 그리고 "java backend junior pizza 150" 위와 같은 문자열이 들어오면 - and - and - and - 1000 - and - and - and pizza 1000 - and - and junior and - 1000 ... 이러한 쿼리의 답에 모두 속하게 된다 그래서 각 info마다 어떤 쿼리의 답이 될 지 모르기 때문에 모든 쿼리에 대한 경우의 수를 모두 구해야겠다고 생각했다. _info = [i.split(' ') for i in info] _query = [] for q in query: a = q.split(' and ') la = a[..

[백준 2143] 두 배열의 합 C++

2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 이분 탐색 1. 문제해결 아이디어 문제에서 정의된 부 배열의 최대 크기는 N(N+1)/2 가 됨을 알 수 있었다. (1~N까지의 합) N, M이 최대 1000이므로 부 배열의 크기는 최대 500,000 이다. 따라서 배열에 담은 후 nlogn 연산이 충분히 가능함을 알 수 있었다. 이분 탐색을 수행하기 위해 subB배열을 정렬한다. T 에서 subA의 원소를 뺀 값이 subB에 있는지 ..

[백준 1300] K 번째 수 C++

1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 이분 탐색 1. 문제해결 아이디어 일단 n이 최대 100000 이므로 B배열을 실제로 만들어 주는건 불가능하다. i번째 행은 i의 배수의 집합임을 이용하자 N = 5, K = 17 이 주어졌을 때. 이 문제를 이분탐색으로 풀기 위해서 5x5의 절반인 12를 최초 mid로 설정하자(lo = 0, hi = 25) 12는 위 표에서 몇 번째일까? 1행은 모두 12보다 같거나 작다 -> cnt += 5 2행도 모두 12보다 같거나 작다 -..

[백준 12015] 가장 긴 증가하는 부분 수열2 C++

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이전까지 풀어봤던 LIS 문제들과 푸는 방법이 조금 다르다 기존LIS는 for문을 2번 돌려서 O(n^2) 시간안에 풀었다면 이번 문제는 수열의 크기가 N st){ int mid = (st + ed)/2; if(key > arr[mid]){ st = mid+1; } else{ ed = mid; } } return ed; } void solve(){ int cnt = 1; res.push_back(arr[0]); for(int i = 1; i