← 질문 목록
#394깊이 0
파라메트릭 서치는 최적화 문제를 어떻게 바꾸어 푸는가?
자료구조 · 알고리즘
답변 연습
내 답변 적어보기접힘
이 브라우저에 자동 저장 · 0자
모범답안 확인하기내 답변 뒤에 열어보세요
최댓값이나 최솟값을 찾는 최적화 문제를 특정 조건을 만족하는지 판별하는 결정 문제로 바꾸어 푼다.
| 기준 | 최적화 문제 | 결정 문제 |
|---|---|---|
| 질문 형태 | 조건 X를 만족하는 최댓값은? | 값 K는 조건 X를 만족하는가? |
| 해법 접근 | 모든 경우를 직접 비교한다 | 이분 탐색으로 범위를 줄인다 |
정답이 될 수 있는 값의 범위가 정렬되어 있을 때 이분 탐색을 적용한다. 특정 값 K에서 조건이 참이면 탐색 범위를 반으로 줄여나간다.
랜선 연결 최대 길이를 구할 때 쓰인다. 특정 길이 L로 원하는 개수를 만드는지 확인하며 범위를 넓히거나 좁힌다.
조건 만족 여부가 단조성을 띠지 않으면 이 방식을 쓰지 못한다. 특정 시점을 기준으로 성공과 실패가 경계선처럼 갈라져야 한다.