수_찾기

[C++] 백준 1920번 수 찾기

이런 문제를 보면 바로 이분탐색부터 떠올려야 한다. big-O 표기법에 따르면 탐색 알고리즘에서 가장 시간소요가 적은 것이 O(NlogN)인데 쉽게 접근할 수 있는게 이분탐색이다. STL 제약이 없기 때문에 vector에 값들을 넣은 후 algorithm STL을 사용해서 sort와 binary_search 메서드를 사용했다. 이렇게 풀면 정말 가볍게 풀 수 있지만 이분 탐색 정도는 구현을 하라는 목적인 것 같았다. head와 tail (보통 left와 right로 표현하는 것 같다.) 그리고 mid를 정해놓고 남은 살펴볼 개수를 절반씩 줄여나가는 방식이다. 물론 STL을 사용할 수 있다면 그냥 algorithm STL을 사용해서 만들면 된다. (사실 STL 없이 sort하라고 하면 정말 답없을 것 같다..