[탐색] Parametric Search

Parametric Search

최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN)

ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다.

Binary Search (이분 탐색)

※ 이분 탐색할 때 보통 데이터가 정렬된 상태이어야 합니다.

 

예시

[BOJ] 2110 공유기 설치 

[BOJ] 백준 2110 공유기 설치

에 총 N개의 집이 있으며, 한 집에 한 개의 공유기를 설치가능.

공유기 C개를 설치할 때, 가장 인접한 두 공유기(집) 사이의 거리를 최대로 하기.

▶ 두 집사이의 거리(간격)을 기준(mid)으로 공유기 개수 C를 만족하는지 확인

▶ 원하는 조건을 만족하는 가장 알맞는 값을 특정한 오차범위 이내에서 알고 싶은 경우

   (범위는 문제조건 마다 다릅니다.)

 

구현

- Lower Bound: (최소값을 구하는 경우) 최소값이 x라면, x이상의 값에 대해서는 모두 조건을 만족

int solve() {
    int start = MIN, end = MAX, mid, sol = 0;
    while (start <= end) {
        mid = (start + end) / 2;
        if (isPossible(mid)) {
            sol = mid; end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return sol;
}

 

- Upper Bound: (최대값을 구하는 경우) 최대값이 x라면, x이하의 값에 대해서는 모두 조건을 만족

int solve() {
    int start = MIN, end = MAX, mid, sol = 0;

    while (start <= end) {
        mid = (start + end) / 2;
        if (isPossible(mid)) {
            sol = mid; start = mid + 1;
        }
        else end = mid - 1;
    }
    return sol;
}

※ Lower/Upper Bound를 결정하였다면 isPossible() 함수를 구현하는 것 중요합니다.

   ▷ Binary Search + YES / NO Problem

 

Binary Search vs Parametric Search

Binary Search: 배열에서 중앙값(middle)이 가리키는 값이 내가 찾는 값인지 중요

Parametric Search: 원하는 조건을 만족하는 가장 알맞는 값을 찾는 것

 

Reference

- [BOJ] 2110 공유기 설치 

- [BOJ] 3090 차이를 최소로 

- [BOJ] 2613 숫자 구슬 

- [BOJ] 2805 나무 자르기 

- [BOJ] 2792 보석상자 

- [BOJ] 1654 랜선 자르기 

- [Jungol] 1156 책 복사하기2 

- [Jungol] 1240 제곱근 

- [SWEA] 3814 평등주의 

- [SWEA] 8569 개미 관찰 

- [SWEA] 3813 그래도 수명이 절반이 되어서는....