[알고리즘&코딩테스트] 매개 변수 탐색 (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);
   }
}