자료구조 | 알고리즘/탐색(Brute Force)2023. 12. 11. 13:35[알고리즘] Parametric Search(매개변수 탐색)
최적화(최대 or 최소)문제를 결정 문제로 바꾸어서 푸는 기법이다. 의심: 완전탐색, DP, 그리디로도 해결할 수 없는 최적화문제의 경우에 두 데이터간의 관계가 단순 비례 반비례에 따른 증감이며 Parameteric Search를 의심해볼 수 있다. 보통 감을 잡기가 매우 어려워서 나중에 돌아와서 떠올리면 베스트 파라메트릭 서치는 STL을 직접 이용할 수 있는 이분탐색과 달리 직접 변수를 설정하고 관계에 따라서 탐색의 범위를 지정해주어야 한다. ??? 예제: 랜선 자르기 백준 1654 주의 사항: 1. 무한 루프 주의: mid를 기준으로 선택의 범위가 균등한지 만약 균등하지 않다면 mid+1로 보정해줘서 무한루프를 방지해줘야함 2. 두 변수간의 관계주의: parameter과 target간의 관계(비례 반..