[알고리즘] 매개변수 탐색(Parametric Search)

이번시간에는 매개변수탐색에 대해서 알아보겠습니다.

 

매개변수탐색이라는 단어가 좀 낯설 수 있는데, 이 방법은 조건을 만족하는 최대값을 구하는 방법입니다. 저는 이 방법을 조건을 만족하는 가장 큰 값, 마지노선 값이라고 생각하고 있습니다.

 

일단 무슨말인지 모르겠으니깐, 예를 한번 들어보겠습니다.

높이가 20 15 10 17인 나무들이 있고 영호는 n높이에서 모든 나무를 일직선으로 잘라서, 최소 7m의 나무를 가져가고 싶어합니다.

단, 여기서 영호는 환경을 생각하기 때문에 나무를 필요한 만큼만 가져 갑니다.

 

13높이 : 7+2+0+4 -> 13m의 나무를 가져갈 수 있습니다. 영호는 환경을 생각하기 때문에 높이를 좀 더 올려보겠습니다.

15높이 : 5+0+0+2 -> 7m의 나무를 가져갈 수 있습니다. 영호는 필요한 만큼만 가져가기 때문에 나무를 자르는 높이는 15m입니다.

 

앞서 매개변수는 조건을 만족하는 최대값을 구하는 방법이라고 했습니다. 

여기서 조건은 최소7m의 나무입니다. 높이h는 다양하게 있을 수 있지만, 조건을 만족하는 최대높이값을 구하는게 문제의 핵심입니다.

 

매개변수 탐색은 내부적으로 이진탐색을 사용하고, start와 end라는 변수를 사용합니다. 여기서 start와 end의 정의가 무척 중요한데

start는 무조건 되는 경우, 즉 나무를 무조건 가져갈 수 있는 경우이므로 0이 됩니다. 0높이에서는 나무를 무조건 가져갈 수 있습니다.

end는 무조건 안되는 경우, 즉 무조건 나무를 가져갈 수 없는 경우이므로 나무중에 가장 큰 값이 됩니다. 위의 경우에서 20높이에서 나무를 자르면 절대 나무를 가져갈 수 없기 때문입니다.

 

import java.util.*;

public class Main {

    static int[] arr;
    static int m;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[n];
        int max = 0;

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int start = 0; // 무조건 나무를 가져갈 수 있는 부분
        int end = max; // 무조건 나무를 가져갈 수 없는 부분

        while (start + 1 < end) {
            int mid = (start + end) / 2;

            if (check(mid)) { // mid위치에서 나무를 가져갈 수 있는지 없는지 확인, 가져갈 수 있다면 mid는 start에 없다면 end에 넣음
                start = mid;
            } else {
                end = mid;
            }
        }

        System.out.println(start);
    }

    static boolean check(int cuttingHeight) { // cuttingHeight위치에서 나무를 가져갈 수 있는지 없는지 확인

        long sum = 0;
        long result;
        long tree;

        for (int i = 0; i < arr.length; i++) {
            tree = arr[i];
            if (tree >= cuttingHeight) {
                result = tree - cuttingHeight;
                sum += result;
            }
        }
        if (sum >= m) {
            return true;
        } else {
            return false;
        }
    }
}

 20 15 10 17높이의 나무가 있는 경우 start=0, end=20이 됩니다.

그렇다면 start와 end의 중간값에서 나무를 잘랐을 때, 최소 7높이의 나무를 가져갈 수 있는지 검사해 봅시다.

 

mid 10 : 10+5+0+7 -> 22

10높이에서 나무를 잘랐을 때 그 합이 7보다 크기 때문에 true네요. 여기서 중요한데, start는 무조건 나무를 가져갈 수 있는 값이라고 했습니다. 그렇다면 방금 10에서 검사해보니 무조건 나무를 가져갈 수 있었죠 ? 그렇다면 start에 10을 넣어줍니다. 10에서도 무조건 가져갈 수 있으니깐요.

 

mid 15 : 5+0+0+2 ->7

15높이에서도 최소7높이의 나무를 가져간다는 조건을 만족하기 때문에 start에 mid값을 넣어줍니다.

 

.............

 

이후의 경우는 모두 조건을 만족하지 않기 때문에 최종 start값은 15가 됩니다. 여기서 start의 정의는 무조건 나무를 가져갈 수 있는 부분이기 때문에 답은 start가 됩니다.

 

여기서 이런 생각을 할 수 있습니다. 진짜 start가 최소7높이의 나무를 가져가는 최소값인가 ? 즉 start높이로 잘랐을 때, 그 합이 7이거나 7에 가장 가까운 값인가? 라는 생각이 들 수 있습니다. 사실 저도 처음에 그런 생각이 들었습니다.

 

사실 while문이 반복되면서 계속 최대값을 찾고있습니다. 왜냐하면 한번 루프를 돌때마다 검사하는 구간이 수정되기 때문입니다. 처음에는 0~20에서 그 다음에는 10~20,그 다음에는 15~20으로 반복되기 때문에 결국에는 start는 조건을 만족하는 최대값을 가질 수 밖에 없습니다.

 

사실 1부터 20까지 하나씩 대입하면서 최대값을 구할 수 있습니다. 하지만, 이는 비효율적이죠 하나씩 다 탐색해야 하기 때문에. 7높이에서 조건을 만족한다면 7보다 작은 값에서는 무조건 값을 만족하기 때문에 그 구간을 조금씩 좁혀나갈 수 있습니다. 여기서 이진탐색의 개념이 사용되는 것입니다.

 

지금까지 매개변수 탐색을 알아봤는데, 여러 문제를 풀어보면서 중요한 부분은 start와 end의 정의를 정확히 내려주는 것이 중요합니다. 또한 조건을 검사하는 함수에서 어떤 논리적으로 풀어나갈지가 가장 중요한 것 같습니다.