---------------------- ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- ---------------------- 문제 접근 순서. 1. 어떠한 값의 범위를 두고 그 조건에 맞는 최대값을 찾는 문제이므로 "이진 탐색 (Binary_Search)" 를 생각함. 2. 이진탐색으로 했을시 - 1번. 인덱스로 접근할지 ( 수가 연속되지 않을 때 ) - 2번. 연속된 수의 범위에서 접근할지 ( 연속되는 수가 가능할 때 ) 3. 여기서는 예산 삭감에대한 비용이 연속적인..

이진 탐색이란?- 정렬된 데이터에서 원하는 값을 빠르게 찾는 알고리즘 탐색 범위를 절반씩 줄여가며 찾기 때문에 O(log N) 의 시간 복잡도를 가진다. 이진 탐색 원리- 이진 탐색은 오름 차순 또는 내림차순으로 정렬된 배열에 적용 가능한 탐색 기법이다. 정렬된 배열에서 특정 값을 찾을 때 중앙에 위치한 값을 활용하면 아주 빠른 속도로 탐색을 끝낼 수 있다. 아래 그림을 보자. 배열을 오름차순으로 정렬되어 있다고 가정한다. 배열의 시작점과 끝점의 정중앙에 위치한 값을 '중앙값'이라고 하고, 만약에 그림과 같이 '탐색값 '탐색값 > 중앙값' 이라고 하면 시작점의 값이 중앙값의 +1을 더해준 위치가 된다. 만약 '탐색값 == 중앙값' 이라면 탐색을 종료한다. 예시1) ..