목록이분탐색 (1)

코딩뚠뚠

[삼성역량테스트PRO] Binary Search

역량테스트 Pro 에만 나오는 개념이라서 여기에 포스팅한건 아니다 물론 자료구조시간에, A형 공부를 하면서도 배운 내용이지만 정리하지 않아서 해본다. 정의 정렬되어 있는 배열에서 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 시간복잡도는 O(logN) 이다. 활용 STL을 사용할 경우 algorithm 헤더의 binary_search, lower_bound, upper_bound를 사용할 수 있다. 이들은 오름차순 정렬되어있는 배열, vector에서만 정상작동한다. 아래 문제에서 활용해보자. 문제 백준 1920번 문제를 직접 구현을 통해 / STL을 사용한 두 가지 방법으로 풀어본다. 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1],..
알고리즘 문제풀이/삼성역량테스트PRO 2022. 4. 15. 23:39
이전 Prev 1 Next 다음