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

이런 문제를 보면 바로 이분탐색부터 떠올려야 한다.

big-O 표기법에 따르면 탐색 알고리즘에서 가장 시간소요가 적은 것이 O(NlogN)인데 쉽게 접근할 수 있는게 이분탐색이다.

STL 제약이 없기 때문에 vector에 값들을 넣은 후 algorithm STL을 사용해서 sort와 binary_search 메서드를 사용했다.

 

이렇게 풀면 정말 가볍게 풀 수 있지만 이분 탐색 정도는 구현을 하라는 목적인 것 같았다.

이분탐색 메서드

head와 tail (보통 left와 right로 표현하는 것 같다.)

그리고 mid를 정해놓고 남은 살펴볼 개수를 절반씩 줄여나가는 방식이다.

물론 STL을 사용할 수 있다면 그냥 algorithm STL을 사용해서 만들면 된다.

(사실 STL 없이 sort하라고 하면 정말 답없을 것 같다...)

사용한 라이브러리와 변수

algorithm STL을 사용해서 sort와 binary_search를 사용한다.

• sort(시작, 끝) / sort(시작, 끝, 비교메서드) 이런 식으로 사용한다.
• binary_search(시작, 끝, 찾는 값) 이런 식으로 사용한다.

vector로 입력받는다. n개를 입력받으며 m번 탐색한다.

tmp는 그냥 값 입력 받을 때 쓰는 변수이다.

메인함수(binary_search 미 구현시)

신기하게도 아래가 binary_search를 STL에서 사용했을 때이고 위가 binary_search를 구현했을 때인데 STL 사용안했을 때가 더 시간이 빠르게 나왔다.

 

이분 탐색인 걸 바로 알면 어렵지 않았던 문제인 것 같다.

STL 없이 정렬, vector를 구현하는 법도 알면 도움이 많이 될 것 같다.

 

kimyunseok/study-record

코드 전문은 위에서 확인할 수 있다.