04. 이분탐색-매개변수탐색

이분탐색 / 매개변수 탐색

Summary

정렬된 배열에서 위치를 찾으면 이분탐색,
“가능한 최대/최소 정답”을 찾으면 매개변수 탐색이다.

---

lowerBound / upperBound 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());
 
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(arr);
        int lower = lowerBound(arr, target);
        int upper = upperBound(arr, target);
 
        System.out.println(lower);
        System.out.println(upper);
        System.out.println(upper - lower);
    }
 
    static int lowerBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
 
        while (left < right) {
            int mid = left + (right - left) / 2;
 
            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }
 
        return left;
    }
 
    static int upperBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
 
        while (left < right) {
            int mid = left + (right - left) / 2;
 
            if (arr[mid] <= target) left = mid + 1;
            else right = mid;
        }
 
        return left;
    }
}

---

매개변수 탐색 검증 템플릿

Info

can(mid)가 true/false로 단조롭게 갈리는지 먼저 확인한다.

import java.io.*;
import java.util.*;
 
public class Main {
    static int k, need;
    static long[] cables;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());
        need = Integer.parseInt(st.nextToken());
 
        cables = new long[k];
        long max = 0;
        for (int i = 0; i < k; i++) {
            cables[i] = Long.parseLong(br.readLine());
            max = Math.max(max, cables[i]);
        }
 
        long left = 1;
        long right = max;
        long answer = 0;
 
        while (left <= right) {
            long mid = left + (right - left) / 2;
 
            if (canMake(mid)) {
                answer = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
 
        System.out.println(answer);
    }
 
    static boolean canMake(long length) {
        long count = 0;
        for (long cable : cables) {
            count += cable / length;
        }
        return count >= need;
    }
}

---

문제 신호

표현	의심
최댓값을 최소화	매개변수 탐색
최솟값을 최대화	매개변수 탐색
가능한 가장 큰 길이	매개변수 탐색
정렬된 값에서 개수 찾기	lower/upperBound
예산, 입국심사, 공유기, 랜선	매개변수 탐색

---

주의점

mid = left + (right - left) / 2
정답 후보를 answer에 저장
can(mid)가 true면 어느 쪽으로 갈지 문제마다 결정
빈 배열, 중복 값, target 범위 밖 확인

---

백지 복원

1. lowerBound와 upperBound의 조건 차이는?
2. 매개변수 탐색에서 can(mid)가 가져야 하는 성질은?
3. 최대 길이를 찾을 때 true면 left/right 중 어디를 움직이는가?