[알고리즘] Parametric Search(매개변수 탐색)자료구조 | 알고리즘/탐색(Brute Force)2023. 12. 11. 13:35
Table of Contents
728x90
반응형
최적화(최대 or 최소)문제를 결정 문제로 바꾸어서 푸는 기법이다.
의심: 완전탐색, DP, 그리디로도 해결할 수 없는 최적화문제의 경우에 두 데이터간의 관계가 단순 비례 반비례에 따른 증감이며 Parameteric Search를 의심해볼 수 있다. 보통 감을 잡기가 매우 어려워서 나중에 돌아와서 떠올리면 베스트
파라메트릭 서치는 STL을 직접 이용할 수 있는 이분탐색과 달리 직접 변수를 설정하고 관계에 따라서 탐색의 범위를 지정해주어야 한다. ???
예제: 랜선 자르기 백준 1654
주의 사항:
1. 무한 루프 주의: mid를 기준으로 선택의 범위가 균등한지 만약 균등하지 않다면 mid+1로 보정해줘서 무한루프를 방지해줘야함
2. 두 변수간의 관계주의: parameter과 target간의 관계(비례 반비례)에따라 오른쪽 왼쪽탐색할지 매우 중요
728x90
반응형
'자료구조 | 알고리즘 > 탐색(Brute Force)' 카테고리의 다른 글
| [알고리즘] 가장 긴 증가하는 부분 수열 O(n log n) (이분 탐색 풀이) (1) | 2023.12.18 |
|---|---|
| [알고리즘] 두 포인터 (0) | 2023.12.16 |
| [알고리즘] 이분 탐색 (1) | 2023.12.06 |
| 브루트 포스(완전 탐색) 알고리즘 (0) | 2023.10.31 |
| 투 포인터 (0) | 2023.10.30 |
@BE_개발자 :: 경이로운 개발일기
경이로운 BE 개발자가 되기 위한 프로그래밍 공부 기록장
도움이 되었다면 "❤️" 또는 "👍🏻" 해주세요! 문의는 아래 이메일로 보내주세요.
![[알고리즘] 두 포인터](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F8RtvQ%2FbtsB7jV7Sw1%2FOGItx62Fz75bI2EZTkb8N0%2Fimg.png)