[JAVA/알고리즘] 이진 탐색 알고리즘을 이용한 문제해결

이진 탐색(Binary) 알고리즘을 이용해서 해결해야 하는 문제 유형은 비슷하다. 주로 최대/최소를 물어본다.

 

1. lt 와 rt를 정했을 때, lt ~ rt 사이에 분명 답이 있다는 확신
2. mid = (lt+rt)/2 가 답으로써 가능한 숫자인지 검증
3. 최대/최소를 구해야 하므로 더 나은 답이 있는지 확인

 

몇 가지 알고리즘 문제를 통해 알아보자.

 

문제 1

9 3 ( 9가지의 노래를 3개의 DVD에 넣을 때 DVD의 최소용량)
1 2 3 4 5 6 7 8 9 (분)

구하고자 하는 것 : DVD의 최소 용량
lt = 9 : 최소한 9분(제일 긴 노래)을 넣을 수 있어야 한다.
rt = 45 : 최대한 노래 전부는 넣을 수 있어야 한다.
➜ 답(DVD의 용량크기)은 9 ~ 45 사이에 확실하게 있다.

 

mid = (9 + 45) / 2 = 27

 

DVD 하나의 용량이 27이면 답으로써 가능한 숫자인가 검증 ➜ DVD 생성 수를 count하는 함수 생성

• 검증 성공 시, 최소 용량을 찾아야 하므로 왼쪽 부분에서 찾기 rt=mid-1
• 검증 실패 시, 오른쪽 부분에서 찾기 lt=mid+1

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

class Main {
    public int count(int[] arr, int capacity) {
        // 검증 : 해당 DVD 용량(capacity)으로 DVD 몇 장을 담을 수 있는가
        int cnt = 1;
        int sum = 0;

        for (int x : arr) {
            if (sum + x > capacity) {
                // 용량을 넘어서면 DVD 한 개 추가.
                cnt++;
                sum = x;
            } else {
                sum += x;
            }
        }
        return cnt;
    }

    public int solution(int n, int m, int[] arr) {
        int answer = 0;
        int lt = Arrays.stream(arr).max().getAsInt();
        int rt = Arrays.stream(arr).sum();

        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            // 검증 : mid는 문제가 요구하는 답으로써 가능한가?

            if (count(arr, mid) <= m) {
                // 노래를 담은 용량이 m 과 같거나 작으면 검증성공
                // DVD가 m개 보다 작다는 의미는 m개로도 충분히 노래를 나눌 수 있으므로 검증 성공이다.

                answer = mid;
                rt = mid - 1; // 최소용량을 찾기위해 rt값 조정
            } else lt = mid + 1;
        }
        return answer;
    }
}

---

문제 2

5 3 (5개의 마구간에 3마리 배치)
1 2 8 4 9 (마구간의 좌표)

구하고자 하는 것 : 두 말 사이의 최대거리
lt = 1 : 최소 거리
rt = arr[n-1] : 너무 세세하게 생각X. 그냥 가장 멀리 있는 좌표 선택
➜ 답(두 말의 최대거리)은 lt~rt 사이에 확실하게 있다.

 

mid = (1 + 9) / 2 = 5

가장 가까운 두 말의 거리를 5라고 했을 때, 답이 가능한지 검증 ➜ 말의 배치 수를 count하는 함수 생성

• 검증 성공 시, 최대 거리를 구해야 하므로 오른쪽 부분에서 찾기 lt=mid+1
• 검증 실패 시, 왼쪽 부분에서 찾기 rt=mid-1

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

class Main {

    public int count(int[] arr, int dist) {
        int cnt = 1;
        int ep = arr[0]; // 말은 시작점에 배치
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] - ep >= dist) {
                // 우리가 정한 최대거리(mid)보다 크거나 같으면 말 한마리 배치
                cnt++; 
                ep = arr[i];
            }
        }
        return cnt;
    }

    public int solution(int n, int c, int[] arr) {
        int answer = 0;
        int lt = arr[0];
        int rt = arr[n - 1];

        while (lt <= rt) {
            int mid = (lt + rt) / 2;

            if (count(arr, mid) >= c) { // c마리 보다 더 많이 놓을 수 있다면
                answer = mid;
                lt = mid + 1; // mid보다 최대가 되는 값이 있는가 다시 확인
            } else rt = mid - 1;
        }
        return answer;
    }