[PAST 알고리즘 시리즈] Part 1 — 이분 탐색 심화 (二分探索 発展)

개요

이분 탐색(Binary Search)은 정렬된 데이터에서 특정 값을 찾는 대표적인 알고리즘입니다. 초급~중급 수준에서는 "값의 단조성(단순 증가/감소)에 주목하여 문제를 풀 수 있도록" 학습합니다.

이번 파트에서는 한 걸음 더 나아가, 이분 탐색이 직접 적용되기 어려운 문제를 변형하여 적용하는 테크닉을 다룹니다.

다루는 주제

섹션	주제	핵심 아이디어
1.1	이분 탐색을 적용할 수 있는 문제	판정 문제 + 단조성
1.2	최솟값의 최대화 (최댓값의 최소화)	최적화  → 판정 문제 변환
1.3	평균값 최대화 · 중앙값 최대화	합계값 문제로 변환 후 이분 탐색

1.1 이분 탐색을 적용할 수 있는 문제

핵심 조건

이분 탐색을 적용하려면, 해당 문제가 다음 두 가지 조건을 만족해야 합니다:

1. 판정 문제를 빠르게 풀 수 있다 — 어떤 값 X에 대해 조건을 만족하는지 여부를 빠르게 판별 가능
2. 판정 결과가 단조적으로 변화한다 — 조건을 만족하는 구간과 만족하지 않는 구간의 경계가 딱 한 곳만 존재

이 두 조건이 충족되면, "조건 A를 만족하는 X의 최댓값(또는 최솟값)을 구하라"라는 최적화 문제를 이분 탐색으로 해결할 수 있습니다.

예제: おまかせ (제1회 PAST · M문제)

문제 요약

• N마리의 소유 몬스터와 M마리의 도우미 몬스터가 있음
• 각 몬스터는 질량(A 또는 C)과 마력(B 또는 D)을 가짐
• N + M 마리 중 정확히 5마리를 뽑아 합성 (단, 도우미 몬스터는 최대 1마리)
• 합성 몬스터의 강도 = (마력의 합) / (질량의 합)
• 강도의 최댓값을 구하라

사고 과정

직접 계산의 한계: 모든 조합을 시도하면, 도우미 미사용 시 ${}_NC_5$가지, 도우미 사용 시 ${}_NC_4 + M$가지의 조합이 존재합니다. $5 \leq N \leq 1000$이므로 실행 시간 제한 내에 처리 불가.

부분 문제로 변환: "합성 몬스터의 강도가 X 이상이 되는 조합이 존재하는가?"라는 판정 문제를 풀어봅시다.

5마리의 몬스터를 선택했을 때, 강도가 X 이상이 되려면:

$\frac{(B_a + B_b + B_c + B_d + B_e)}{(A_a + A_b + A_c + A_d + A_e)} \geq X$

이를 변형하면:

$(B_a - A_a X) + (B_b - A_b X) + (B_c - A_c X) + (B_d - A_d X) + (B_e - A_e X) \geq 0$

각 몬스터 $i$에 대해 $P_i = B_i - A_i X$를 계산하면, P 값이 큰 순서대로 5마리를 선택했을 때 합이 0 이상이면 조건을 만족합니다.

알고리즘 정리

1. 각 소유 몬스터 $i$에 대해 $P_i = B_i - A_i X$ 를 계산
2. P를 정렬하여 큰 쪽에서 5개 선택
3. 각 도우미 몬스터 $j$에 대해 $Q_j = D_j - C_j X$ 를 계산
4. 도우미 몬스터를 사용하는 경우: P에서 상위 4개 + Q의 최댓값 1개를 선택
5. 위 두 경우 중 합이 0 이상인 경우가 있으면 → 강도 X 이상 달성 가능

Java 구현 예시

import java.util.*;

public class Main {
    static int N, M;
    static long[] A, B, C, D;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        A = new long[N]; B = new long[N];
        C = new long[M]; D = new long[M];
        for (int i = 0; i < N; i++) { A[i] = sc.nextLong(); B[i] = sc.nextLong(); }
        for (int i = 0; i < M; i++) { C[i] = sc.nextLong(); D[i] = sc.nextLong(); }

        double lo = 0, hi = 1e9;
        for (int iter = 0; iter < 100; iter++) {
            double mid = (lo + hi) / 2.0;
            if (check(mid)) lo = mid;
            else hi = mid;
        }
        System.out.printf("%.13f%n", lo);
    }

    static boolean check(double X) {
        // 소유 몬스터의 P 값 계산
        double[] P = new double[N];
        for (int i = 0; i < N; i++) P[i] = B[i] - A[i] * X;
        Arrays.sort(P);

        // P에서 상위 5개의 합 (도우미 미사용)
        double sum5 = 0;
        for (int i = N - 1; i >= Math.max(0, N - 5); i--) sum5 += P[i];
        if (sum5 >= -1e-9) return true;

        // P에서 상위 4개 + Q의 최댓값 (도우미 사용)
        double sum4 = 0;
        for (int i = N - 1; i >= Math.max(0, N - 4); i--) sum4 += P[i];
        double maxQ = Double.NEGATIVE_INFINITY;
        for (int j = 0; j < M; j++) {
            maxQ = Math.max(maxQ, D[j] - C[j] * X);
        }
        return sum4 + maxQ >= -1e-9;
    }
}

1.2 최솟값의 최대화 (최댓값의 최소화)

개념

"조건 A를 만족하는 수열 B 중, 최솟값이 가장 큰 것을 구하라"는 유형의 문제입니다.

이를 이분 탐색으로 접근하면:

"조건 A를 만족하고, 최솟값이 X 이상인 수열 B를 만들 수 있는가?"

라는 판정 문제를 만들어, X의 값을 이분 탐색으로 결정합니다.

예제: 棒の出荷 (제5회 PAST · M문제)

문제 요약

• 길이가 $A_1, A_2, \ldots, A_N$인 N개의 구간으로 나뉜 긴 막대
• N−1개의 절단 위치 중 일부를 선택하여 절단
• 모든 막대의 길이가 L 이하가 되어야 함
• 가장 짧은 막대의 길이를 최대화하라

왜 "최솟값의 최대화"인가?

길이 S인 막대를 M개로 자유롭게 분할하면, 최솟값의 최대치는 S/M입니다 (모든 조각을 동일하게).

하지만 실제로는 미리 정해진 위치에서만 절단 가능하므로 완전히 균등하게는 만들 수 없습니다. 그래도 이 "균등 분배" 상태를 목표로 합니다.

판정 문제 설계

"절단 후 가장 짧은 막대의 길이가 X 이상인 절단 방법이 존재하는가?"

이 문제를 O(N)에 판정할 수 있다면, 이분 탐색으로 최대의 X를 구할 수 있습니다.

판정 알고리즘 — いもす法(이모스법) 활용

서적에서는 "어떤 절단 위치 i에서 절단한 후, 다음에 절단할 수 있는 범위 [l, r]"을 효율적으로 관리하는 방법을 설명합니다.

핵심 아이디어:

1. 절단 위치의 누적합 배열 S[i]를 전처리
2. 절단 위치 i에서 절단했을 때:
   • 다음 절단까지 최소 X 이상 떨어져야 함 → S[l] - S[i] ≥ X를 만족하는 최소 l
   • 다음 절단까지 최대 L 이하여야 함 → S[r] - S[i] ≤ L을 만족하는 최대 r
3. C[i] = "절단 위치 i에서 절단 가능한가" (도달 가능 여부)

단순 구현은 O(N²)이 되지만, 누적합의 차분 배열(いもす法)을 사용하면 O(N)으로 줄일 수 있습니다.

Java 구현 예시

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long L = sc.nextLong();
        long[] A = new long[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextLong();

        // 누적합 전처리
        long[] S = new long[N + 1];
        for (int i = 0; i < N; i++) S[i + 1] = S[i] + A[i];

        // 이분 탐색: 최솟값의 최대화
        long lo = 0, hi = L + 1;
        while (hi - lo > 1) {
            long mid = (lo + hi) / 2;
            if (check(N, L, S, mid)) lo = mid;
            else hi = mid;
        }
        System.out.println(lo);
    }

    static boolean check(int N, long L, long[] S, long X) {
        int l = 0, r = 0;
        int[] C = new int[N + 1];
        int[] D = new int[N + 1]; // 차분 배열

        D[0] += 1;
        if (1 <= N) D[1] -= 1;

        for (int i = 0; i < N; i++) {
            if (i > 0) C[i] = C[i - 1] + D[i];
            else C[i] = D[i];

            if (C[i] == 0) continue;

            // 다음 절단까지 최소 X 이상
            while (l <= N && S[l] - S[i] < X) l++;
            if (l > N) continue;

            // 다음 절단까지 최대 L 이하
            while (r + 1 <= N && S[r + 1] - S[i] <= L) r++;

            // [l, r] 구간에 도달 가능 표시 (いもす법)
            D[l] += 1;
            if (r + 1 <= N) D[r + 1] -= 1;
        }

        C[N] = C[N - 1] + D[N];
        return C[N] > 0;
    }
}

1.3 평균값 최대화 · 중앙값 최대화

개념

"배열에서 조건을 만족하도록 요소를 선택했을 때, 선택한 요소의 평균값 또는 중앙값을 최대화하라"는 유형입니다.

핵심 변환 아이디어:

• 평균값 ≥ X ↔ 각 요소에서 X를 빼서 새 배열 $B_i = A_i - X$를 만들면, B에서 선택한 요소의 합계 ≥ 0
• 중앙값 ≥ X ↔ 각 요소를 $A_i \geq X$이면 +1, 아니면 -1로 변환하여, 변환 배열에서 선택한 요소의 합계 > 0

둘 다 "합계 ≥ 0인 선택 방법이 존재하는가?"라는 판정 문제로 귀결되며, X의 값을 이분 탐색할 수 있습니다.

예제: Average and Median (ABC236 · E문제)

문제 요약

• N장의 카드, i번째 카드에 정수 $A_i$가 적혀 있음
• 카드를 원하는 만큼 선택 (단, 연속 2장을 모두 선택하지 않는 것은 불가 → 인접한 i번과 i+1번 중 적어도 하나는 반드시 선택)
• 선택한 카드의 평균값 최대와 중앙값 최대를 각각 구하라

평균값 최대화 풀이

1. 판정 문제: "평균값이 X 이상이 되도록 선택하는 방법이 존재하는가?"
2. $B_i = A_i - X$ 로 변환하면 → "B에서 선택한 요소의 합계 ≥ 0인 선택 방법이 존재하는가?"
3. "인접한 2개 중 적어도 하나는 선택" 조건 하에서 합계를 최대화하는 것은 DP로 해결

DP 정의:

• $S_{i+1}$ = B의 i번째까지 중, 조건을 만족하면서 i번째를 선택했을 때의 합계 최댓값
• $T_{i+1}$ = B의 i번째까지 중, 조건을 만족하면서 i번째를 선택하지 않았을 때의 합계 최댓값

점화식:

$$S_{i+1} = \max(S_i, T_i) + B_i$$

$$T_{i+1} = S_i$$

중앙값 최대화 풀이

1. $B_i = A_i \geq X$ 이면 1, 아니면 -1
2. 같은 DP로 합계가 0보다 크면 → 중앙값 X 이상 달성 가능
3. 중앙값은 반드시 정수이므로 정수 범위 이분 탐색 사용

Java 구현 예시

import java.util.*;

public class Main {
    static int N;
    static long[] A;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        A = new long[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextLong();

        // ===== 평균값 최대화 (실수 이분 탐색) =====
        double avLo = 0, avHi = 1e10;
        for (int iter = 0; iter < 100; iter++) {
            double mid = (avLo + avHi) / 2.0;
            if (checkAverage(mid)) avLo = mid;
            else avHi = mid;
        }
        System.out.printf("%.13f%n", avLo);

        // ===== 중앙값 최대화 (정수 이분 탐색) =====
        long mdLo = 0, mdHi = 1_000_000_001L;
        while (mdHi - mdLo > 1) {
            long mid = (mdLo + mdHi) / 2;
            if (checkMedian(mid)) mdLo = mid;
            else mdHi = mid;
        }
        System.out.println(mdLo);
    }

    // 평균값이 X 이상이 되는 선택 방법이 존재하는가?
    static boolean checkAverage(double X) {
        double[] B = new double[N];
        for (int i = 0; i < N; i++) B[i] = A[i] - X;

        double[] S = new double[N + 1];
        double[] T = new double[N + 1];
        for (int i = 0; i < N; i++) {
            S[i + 1] = Math.max(T[i], S[i]) + B[i];
            T[i + 1] = S[i];
        }
        return Math.max(S[N], T[N]) >= -1e-9;
    }

    // 중앙값이 X 이상이 되는 선택 방법이 존재하는가?
    static boolean checkMedian(long X) {
        int[] B = new int[N];
        for (int i = 0; i < N; i++) B[i] = (A[i] >= X) ? 1 : -1;

        long[] S = new long[N + 1];
        long[] T = new long[N + 1];
        for (int i = 0; i < N; i++) {
            S[i + 1] = Math.max(T[i], S[i]) + B[i];
            T[i + 1] = S[i];
        }
        return Math.max(S[N], T[N]) > 0;
    }
}

정리

테크닉	핵심 아이디어	판정 문제 형태
이분 탐색 기본 패턴	최적화 문제를 판정 문제로 변환	"X 이상(이하)을 만족하는 해가 존재하는가?"
최솟값의 최대화	min-max를 판정 문제로 전환	"최솟값이 X 이상인 해가 존재하는가?"
평균값 최대화	$B_i = A_i - X$로 변환 후 합계 문제로	"B의 합계 ≥ 0인 선택이 가능한가?"
중앙값 최대화	$B_i = \pm 1$ 변환 후 합계 문제로	"B의 합계 > 0인 선택이 가능한가?"

실전 팁

1. 실수 이분 탐색: 반복 횟수를 100회로 고정하면 안전 ($10^{-30}$ 수준의 정밀도)
2. 정수 이분 탐색: while (hi - lo > 1) 패턴 사용
3. "답을 결정하고 판정"하는 사고법은 이분 탐색 외에도 다양한 곳에서 활용됩니다
4. いもす法(이모스법)은 구간 일괄 갱신을 O(1)로 처리하는 강력한 도구입니다

관련 문제 링크

문제	출처	난이도
おまかせ	제1회 PAST · M	★★★
棒の出荷	제5회 PAST · M	★★★
Average and Median	ABC 236 · E	★★★

참고 자료

• 서적: 「アルゴリズム実技検定 公式テキスト ［上級］～［エキスパート］編」(マイナビ出版, 2023)
• 소스코드: tsutaj/pastbook-2-source-code (Github)
• PAST 공식 사이트: https://past.atcoder.jp
• AtCoder 공식 사이트: https://atcoder.jp