23-07-11 TIL

문제

• 이분 탐색
  • 백준 문제를 푸는데 이분 탐색을 이용한 문제가 나왔다.
  • 해당 문제를 풀기는 했으나 이분 탐색에 대해서 정확히 아는 것이 아니고, 지난주에 풀었던 문제의 답을 보고 시도하였기 때문에 이분 탐색에 대해서 알아보고 기록하고자 한다.
  • 또한 문제에서 답을 upper bound를 골라야하는지, lower bound를 골라야하는지, 혹은 내가 임의로 만들었던 upperBudget 변수를 골라야하는지 혼란이 왔기 때문에 알아보고자 한다.

시도

• 이분 탐색 (백준 참고)
  • 결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색 기법
    -> 결정 문제란 답이 Yes or No인 문제를 의미하며 (이분 탐색 문제에서는) 보통 1개의 parameter를 가진다.
    -> 결정 문제의 답이 두 구간으로 나뉘는 것을 "이분적이다"라고 하며 이런 경우 이분 탐색을 사용해 결정 문제의 답이 달라지는 경계를 찾을 수 있다.
  • 이분 탐색의 아이디어는 경계를 포함하는 구간 [lo, hi]을 잡은 뒤 구간의 길이를 절반씩 줄여나가며 lo, hi이 경계 지점에 위치하도록 하는 것
    -> 구간의 범위가 클 때 특히 효과적
  • 많은 최적화 문제는 이분 탐색으로 풀 수 있다.
    -> 최적화 문제란 어떤 조건(Check(x))을 만족하는 x의 최댓값 또는 최솟값을 찾는 문제
  • 구현 방법
    • Check(lo) != Check(hi)가 되도록 lo, hi의 초기값을 잘 설정
    • lo + 1 < hi인 동안 mid = (lo + hi) / 2를 구함
    • Check(lo) == Check(mid)라면 lo = mid를, Check(hi) == Check(mid)라면 hi = mid
    • lo + 1 == high 가 되면 탈출

해결

• 이분 탐색
  • 백준에 정리되어 있는 이분 탐색 방법을 읽어보고 해당 문제를 풀어보았다.
  • upper_bound를 골라야하는지, lower_bound를 골라야하는지 고민을 했지만 해당 문제에서는 상한액을 고르는 문제이기 때문에 upper_bound를 골라서 해결하였다.
  • 다른 이분 탐색 알고리즘 문제도 찾아서 풀어볼 예정

오늘 푼 문제

• 백준 2512 (예산) - Java
  • 이분 탐색을 이용해서 답을 구하는 문제이다.
  • 이분 탐색에 대해서 정확히 이해하고 활용할 줄 알아야 풀 수 있다.

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 지방의 수
        int number = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 각 지방 예산 저장 리스트
        ArrayList<Integer> budget = new ArrayList<>();

        int low = 0;
        int high = 0;

        for (int i = 0; i < number; i++) {
            int input = Integer.parseInt(st.nextToken());
            // 각 지방 예산
            budget.add(input);
            // 각 지방 예산의 최대 값 -> 이분 탐색의 high 값
            high = Math.max(high, input);
        }

        // 할당 된 예산 총합
        int maxBudget = Integer.parseInt(br.readLine());

        // 이분 탐색
        while (low <= high) {

            int mid = (low + high) / 2;

            long upperBudget = 0L;

            for(int i = 0; i < number; i++) {
                // 해당 예산이 중간값보다 크면 저장할 값에 중간값 더하고
                // 아니면 저장할 값에 해당 예산을 더한다.
                if (budget.get(i) > mid) upperBudget += mid;
                else upperBudget += budget.get(i);
            }

            // 저장할 값이 할당 된 예산 총합보다 작거나 같으면 low를 올려서 더 더해도 됨
            if(upperBudget <= maxBudget) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }

        // 결국 각 지방 예산 최대 값이 상한액이 된다.
        bw.write(high + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}