[백준 1920번 C++] 수 찾기
대표적인 탐색 기본 문제이다. 기본적으로 투포인터나 이분 탐색 알고리즘을 통해 찾을 수 있지만, 본 문제는 이분탐색 알고리즘을 활용해 풀었다. 참고로 이분 탐색과 투포인터 알고리즘의 차이점은 다음과 같다. 이분 탐색(이진 탐색) 투포인터 시간복잡도 O(log N) O(N) 방식 mid를 사용해 연산마다 탐색해야하는 데이터를 절반으로 줄임(log N) 양 끝단(혹은 첫 인덱스에서)시작하여 한칸씩 이동하며 적절한 값을 찾음 조건 데이터가 정렬된 상태에서 가능 상관 없음 투포인터 알고리즘의 경우 양끝단(혹은 첫 인덱스)에서 시작하여 한칸씩 이동하며 알맞은 값을 찾기 때문에 구간 합을 구할 때 유용하게 사용할 수 있다. 이분탐색 알고리즘은 특정한 값을 찾고자 할때 인덱스의 중간값을 사용하여 찾고자하는 값과 비교..
2022.07.21