[알고리즘&코딩테스트] 매개 변수 탐색 (Parametric Search)

매개 변수 탐색(Parametric Search)란?

· 이진 탐색(이분 탐색)을 사용하여 조건을 만족하는 최대값을 구하는 방법이다.

 

· 핵심

1. 정답을 매개 변수로 만들고, Yes/No 문제(결정 문제)로 바꿔 보기

2. 모든 값에 대해서 Yes/No를 채웠다고 생각했을 때, 정렬된 상태인가?

3. Yes/No를 결정하는 문제로 풀기

 

· 문제를 거꾸로 푸는 것이기 때문에 통찰력이 요구된다.

· 최근 코딩테스트 빈도로 굉장히 높게 나온다.

· 키워드에 "~~의 최댓값/최솟값 을 구하시오"가 포함되면 매개 변수 탐색을 접근해볼 가치가 있다. 

 

· 자주 하는 실수

1. 매개 변수에 대한 결정이 Nooooooo Yessssss 꼴이 아닌데 이분 탐색을 하는 경우

2. L, R, M, Result 변수의 정의를 헷갈려서 부등호 등을 잘못 쓰는 경우

3. L, R 범위를 잘못 설정하거나 Result의 초기값을 잘못 설정하는 경우

 

· 관련 문제

- BOJ 2805 - 나무 자르기

- BOJ 1654 - 랜선 자르기

- BOJ 2512 - 예산

- BOJ 2110 - 공유기 설치

- BOJ 2343 - 기타 레슨

- BOJ 6236 - 용돈 관리

- BOJ 13702 - 이상한 술집

- BOJ 17266 - 어두운 굴다리

- BOJ 1300 - K 번째 수 (고난이도)

- BOJ 1637 - 날카로운 눈 (고난이도)

 

예제 1

· BOJ 2805 - 나무 자르기 https://www.acmicpc.net/problem/2805

· 문제 파악

- 나무 개수 N = 100만, 필요한 나무 길이 M = 20억

- 잘린 나무의 길이 합 <= 나무 높이의 총합 = 100만 x10억 -> 즉, 계산 과정 중의 변수 타입은 long을 사용해야함

- 뒤집은 문제: 어떤 높이(H)로 잘랐을 때, 원하는 길이 M 만큼을 얻을 수 있는가?

· 시간 복잡도: O(NlogX)

1. H를 정해서 결정 문제 한 번 풀기 => O(N), 2. 정답의 범위를 이분 탐색하면서 풀기 =>  O(logX)번 반복

 

public class BOJ2805나무자르기 {
    static int N;
    static int M;
    static int[] trees;
    
    public static void main(String[] args) {
        input();
        pro();
    }
    
    private static void pro() {
        long H = 0; // 최대 절단기 높이
        long start = 0;
        long end = 2000000000;
        while (start <= end) {
            int mid = (int)((start + end) / 2); // 절단기 높이
            if (determination(mid)) {
                H = mid;
                start = mid + 1; // 더 큰 절단기 중에 조건을 만족하는 것이 있는지 탐색
            } else {
                end = mid - 1;
            }
        }
        
        System.out.println(H);
    }
    
    private static boolean determination(long H) {
        long sliced = 0; // 잘린 목재 길이
        for (int tree : trees) {
            if (tree > H) {
                sliced += tree - H;
            }
        }
        return sliced >= M;
    }
    
    private static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        trees = new int[N];
        for (int i = 0; i < trees.length; i++) {
            trees[i] = sc.nextInt();
        }
    }
}

 

예제 2

· BOJ 2110 - 공유기 설치 https://www.acmicpc.net/problem/2110

· 문제 파악

- 가장 멀리 설치할 경우 정답은 10억 이하 -> Integer로 표현 가능

- 키워드 체크: "가장 인정합 두 공유기 사이의 거리를 최대로"하는 프로그램

- 매개 변수 만들기(뒤집은 문제): 

   - 원래 문제: C개의 공유기를 설치했을 때, 최대 인접 거리(D)는 얼마인가?

   - 뒤집은 문제: 어떤 거리 만큼 거리를 둘 때, 공유기 C개를 설치할 수 있는가? Yes/No

- 총 시간 복잡도: O(NlogN + NlogX)

   1. 주어진 집들을 정렬하기 O(NlogN)

   2.  D를 정해서 결정 문제 한 번 풀기 O(N)

   3. 정답의 범위를 이분 탁색하면서 풀기 O(logX)번 반복

import java.util.Arrays;
import java.util.Scanner;

public class BOJ2110공유기설치 {
    static int N, C;
    static int A[];
    
    public static void main(String[] args) {
        input();
        pro();
    }
    
    private static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        C = sc.nextInt();
        A = new int[N+1];
        for (int i = 1; i < A.length; i++) {
            A[i] = sc.nextInt();
        }
    }
    
    static boolean determination(int D) {
        // D 만큼의 거리 차이를 둔다면 C개 만큼 공유기를 설치할 수 있는가?
        
        // 제일 왼쪽 집부터 가능한 많이 설치해본다.
        // D 만큼의 거리를 두면서 최대로 설치한 개수와 C를 비교한다.
        int cnt = 1, last = A[1];
        for (int i = 2; i <= N; i++) {
            // 이번에 A[i]에 설치가 가능한가?
            if (A[i] - last >= D) {
                cnt++;
                last = A[i];
            }
        }
        return cnt >= C;
    }
    
    static void pro() {
        // determination을 빠르게 하기 위해 정렬
        Arrays.sort(A);
        
        int L = 1, R = 1_000_000_000, ans = 0;
        // [L...R] 범위 안에 정답이 존재
        // 이분 탐색과 determination 문제를 이용해서 answer를 빠르게 구하자.
        while (L <= R) {
            int mid = (L + R) / 2;
            if (determination(mid)) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        System.out.println(ans);
    }
}