https://www.acmicpc.net/problem/1300 이 문제를 풀 때 N의 최댓값이 10^5 이므로 이차원 배열(N x N)을 만들어 문제를 풀면 100억의 메모리가 필요하고, 10^10(log(10^10)) 의 시간이 필요한데 사실상 불가능하다.메모리O(N^2)시간O(N^2 log(N^2)) 이 문제에서 요구하는 것은 "정렬된 배열에서 k번째로 작은 값"이다. 만약 어떤 값 x를 기준으로 배열(B) 에서 x 이하의 원소가 몇 개인지만 구하면 “x 이하가 k개 이상이면 → B[k]는 x 이하여야 함”“x 이하가 k개 미만이면 → B[k]는 x 보다 커야 함”위와 같은 기준을 얻을 수 있고, 이분탐색을 이용해 원하는 B[k]를 빠르게 구할 수 있다. 문제를 보면 이론상으론1 이지만,..
