DevBoi

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 공유기 설치 문제이다. 이전에 풀었던 레슨 문제와 유사하다. 범위를 구하고 이분탐색을 하면 끝이다. 말하면, 각각의 리스트들을 합하듯이, 앞에서 뒤의 집을 빼주면서 체크를 하고, 이분탐색의 mid 값보다 크다면, cnt를 증가, 반복문이 다돌면, answer보다 큰지 작은지 체크해서, 답에 update해주면 된다.

이진탐색에 대한 공부를 시작한다. 이진탐색을 왜쓸까? 일단 이것부터 파악을 해야한다. 사실 순차 탐색 = 이진탐색 값을 구하는 건 동일하다. 결국 둘다 탐색을 해서 답을 도출해내는 건 동일하게 성공적으로 실행된다. 근데, 탐색해야되는 량이 엄청 많다면? 그때는 이진탐색을 실행한다. 우선 이진탐색에 대한 기초적인 구현을 시작한다. 아주 간단하게, 5개의 숫자를 입력받고, 그중에 target인 15를 찾는것이다. mid를 시작과 끝점을 합한 /2 를 하고, 만약의 mid index가 타겟보다 크면, 최고를 mid -1 로 이동 반대라면 low를 mid +1로하게된다. 물론 이 것은 입력값이 순차적은 정렬 형태를 띈다는 가정이다. 이렇게 되면 순차 탐색 보다 훨씩 빠른 탐색을 할수있다. 탐색 대상이 많은 경우..