정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/7469 7469번: K번째 수 문제 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. www.acmicpc.net 1. 풀이 merge sort tree + binary search 쿼리마다 각 구간에서 어떤 수 보다 작은 수의 개수가 k-1개 인 것 중 가장 큰 수를 이분 탐색으로 찾는다. 2. 풀이 코드 * 유의할 점 #include const int INF = 1e9+7; const int NMAX = 100005; const int MAX = 1 =1;i--){ vector &c = tree..

0. 문제 주소 https://www.acmicpc.net/problem/2143 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)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다. www.acmicpc.net 1. 풀이 먼저 A와 B 배열에 대해, 가능한 모든 부배열의 합을 구해 놓는다. 우리가 원하는 상황은, A의 부배열 합 + B의 부배열 합 = T가 되는 상황이다. A의 부배열 ..