[알고리즘] 이분탐색 : 파라메트릭 서치 (Parametric Search)

개념 완전 탐색으로 해결하는 경우 시간 초과가 날 때 이분탐색 (파라메트릭 서치)를 이용하면 해결되는 경우가 많음. 이분 탐색이란, 정렬된 배열이 있을 때 중간부터 탐색을 시작하여 탐색할 문제를 점차 반씩 줄여나가는 방식이다.

중요한 점 1. 먼저 정렬되어 있는지 확인하고 정렬되어 있지 않다면 정렬부터 수행 2.

문제에서 구하라고 하는 값의 범위를 고려해서 이분 탐색의 범위로 할당 파라메트릭 서치 (Parametric Search) 란? - 최적화 문제(문제의 상황을 만족하는 특정 변수의 최소값, 최대값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것 - 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이분 탐..........