솔

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 이지만,..

이진 탐색이란, 정렬되어있는 데이터가 주어졌을 떄 사용 가능한 정렬 방식입니다. 이러한 배열이 주어졌을 때, 7이라는 숫자를 이진 탐색으로 찾는 과정을 살펴봅시다.가장 첫번쨰 인덱스 (0번) 과 가장 마지막 인덱스(9번)의 평균 4 ((0+9)/2) 번 인덱스를 봅니다. 찾고자하는 7은 5보다 크기 때문에, 왼쪽 절반을 다 탐색 범위에서 없앱니다.  그리고, 새로운 탐색 범위의 중간값을 살펴봅니다.7은 8보다 작기 때문에 8을 기준으로 오른쪽 부분도 없앱니다.또, 새로운 범위의 중간값을 봅니다.6보다 7이 더 크기 때문에 6을 탐색범위에서 없앱니다.이제, 탐색이 끝났습니다. 만약 찾을 수 없는 숫자를 탐색하고자 한다면, 위와 같이 숫자가 1개 남아도 탐색이 완료되지 않겠죠.  이것까지 고려해서 코드를 짜..