알고리즘 - 이분탐색(Binary Search)과 매개변수 탐색(Parameter Search) (Java, Python)

1. 이분탐색

1) 개념

원하는 데이터를  찾기 위해 정렬되어 있는 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

이를 위해 반드시 데이터가 정렬되어 있어야 한다.

 

2) 알고리즘 단계

1. 배열을 정렬한다. ( 기존에 배열이 정렬되어서 주어진다면 이 과정은 생략한다.)

2. start와 end 값으로 탐색하고자 하는 범위를 지정한다.

3. start와 end 값에 따라 mid 값이 정해진다. ( mid = (start+end)/2)

4. 배열의 mid 위치에 있는 데이터와 찾고자 하는 데이터가 일치하는지 확인한다.

4 - 1. 일치한다면 탐색이 종료된다.

4 - 2. mid 위치의 값이 목표값보다 작다면, 주어진 배열은 정렬되어 있으므로 mid 위치보다 오른쪽에 있다. 따라서 start값을 mid+1로 조정 후 3번 과정으로 되돌아가 반복한다.

4 - 3. mid 위치의 값이 목표값보다 크다면, mid 위치보다 목표값이 왼쪽에 있다는 의미이므로 end 값을 mid -1로 조정 후 위 과정을 반복한다. 

5. 4번을 반복해도 목표값이 나오지 않는 경우 start가 end보다 커지게 되며, 이렇게 종료될 경우 배열 내에 원하는 값이 없음을 의미한다.

 

 

 

3) 주의할 점

이분탐색의 개념은 매우 쉽다. 하지만 실제로 구현하다 보면 while문 내에서 무한루프를 돌게 되는 상황을 자주 만날 수 있다. 그 이유는 start와 end 값의 설정이나 while문 내의 조건이 start < end 혹은 start <=end , start +1 < end 등에 따라 mid가 한 쪽으로 치우쳐 mid로 탐색하지 못하는 인덱스가 생기는 상황들이 발생하기 때문이다.

나 또한, 이런 문제들로 이분탐색에서 자주 헤매곤 해서 이 부분에 대해 이 글을 통해 확실히 정리하고 넘어가려고 한다. 

 

우선 이분탐색의 단계를 구분하기 위해 아래와 같이 메서드를 구분하겠다.

- binary_search(int target) : 찾고자 하는 수를 이분탐색으로 찾는 메서드

- check(int mid) : 주어진 값이 원하는 조건에 맞는지 확인하는 메서드

 

따라서 binary_search 메서드 내에서 check 메서드를 활용해, mid값을 찾았는지, start와 end 값을 어떻게 조정할 지를 정한다.

 

우선 binary_search의 start와 end 값은 아래 조건을 만족하도록 고려하여 설정한다.

- check(start) != check(end)

 

 

그 후 while(start+1 < end) 동안 start와 end 값의 변동은 어떻게 해야할까?

check(mid)값이 동일한 쪽의 값을 mid로 바꾼다.

 

즉, check(mid) == check(start)라면 start 값을 mid로, check(mid) == check(end)라면 end를 mid로 변경하도록 구현한다. 

start와 end 값을 초기에 다르도록 설정했기 때문에 check(mid)는 반드시 양 쪽 중 어느 하나랑 값이 일치하게 되며, 일치하는 쪽을 새로운 끝값으로 설정하므로 여전히 check(start)!=check(end)가 유지되게 된다.

 

 

 

마지막으로, 구한 경계에서 답이 start인지 end인지 판별 후 답을 return한다. 

 

첫 단계에서 check(start)!=check(end)가 되도록 start와 end를 설정했으므로 두 값이 바뀌는 경계가 범위 내에 반드시 존재하게 된다. 이 후 start와 end 값을 변동하는 과정을 살펴보면, 양 끝의 check 값이 변동되지 않도록 탐색 범위를 절반씩 줄여나감을 알 수 있다. 

따라서 이렇게 범위를 줄여나가다 보면, start+1>=end가 되는 경계까지 오게 되며, 이때는 binary_search 메서드의 while문이 종료되게 된다. 또한 줄여나가다 만난 경계는 start<mid<end를 만족하므로 start+1==end를 만족하게 된다. 

 

 

 

그럼 이제 위 과정을 반영하여 백준의 2805번 나무자르기를 통해 구체적인 예시로 살펴보겠다. 

 

https://www.acmicpc.net/problem/2805

 

우선 주어진 문제는 주어진 조건을 만족하는 절단기의 높이의 최댓값을 찾아야한다. 따라서 다음과 같은 과정을 통해 check를 구현하고, start와 end값을 조정해나간다.

 

1. 내가 구한 높이가 절단 조건을 충족하는지에 대해 확인하는 check(int mid) 메서드를 세운다. 따라서 가장 낮게 잡을 수 있는 높이인 0을 잡게 되면 절단한 나무의 길이 합이 주어진 조건 M보다 커지기 때문에 true가 반환될 것이며, 가장 높은 나무의 길이를 잡게 되면 절단된 나무 길이 합이 M보다 작아져 false가 반환될 것이다.

 

2. check(start) = true , check(end) = false가 되도록 초기 start와 end값을 설정한다. 1번에서의 설명처럼 start = 0, end = 가장 높은 나무의 길이가 설정될 것이다.

 

3. mid 값을 체크하여 check(mid)가 true가 나온다면 true 쪽 경계였던 start의 값을 변경( start = mid) 하여 더 큰 mid 값을 찾기 위해 범위를 좁혀나간다. 반면, check(mid)가 false가 나온다면 false  쪽 경계였던 end값을 변경(end = mid)하여 true인 값을 찾기 위해 범위를 좁힌다. 

 

** 이 때 while문의 조건은 start와 end 사이의 다른 빈칸이 존재하는 지를 체크할 수 있도록 start+1<end로 두게 된다. 

 

따라서 위 과정을 코드로 구현하면 아래와 같다. 

    public static void main(String[] args) throws IOException {
        input();

        int answer = binary_search();

        System.out.println(answer);
    }

    public static int binary_search(){
        int start = 0 ;
        int end = Arrays.stream(arr).max().getAsInt();

        while(start + 1 < end){
            int mid = (start + end)/2;
            if(check(mid)) start = mid;
            else end = mid;
        }

        return start;
    }

    public static boolean check(int mid){
        long sum =0;
        for(int i=0; i<N; i++){
            if(arr[i]>mid) sum+= arr[i]-mid;
        }

        return sum>=M;
    }

 

 

 

2. 매개변수 탐색

매개변수 탐색은 이분탐색과 그 원리는 동일하다. 다만, 이진탐색은 특정값이 범위 내에 존재하는 특정 위치를 찾는다면, 매개변수 탐색은 특정 조건을 만족하는 처음 위치를 찾는 문제이다. 이분탐색과 마찬가지로 배열이 정렬되어 있어야 한다.

 

쉽게 생각하면, 정렬된 해당 배열에 어떤 값을 집어넣어도 정렬이 유지되도록 할 때, 그 원소를 넣을 수 있는 가장 왼쪽 위치또는 오른쪽 위치를 탐색하는 방식이 매개변수 탐색이다.

 

오름차순으로 정렬된 배열에서 가장 왼쪽 인덱스를 찾는 방식을 lower_bound, 가장 오른쪽 인덱스를 찾는 방식을 upper_bound라고 칭한다.

개인적으로 초반에는 index와 초과 이상 여러가지 말들로 매개변수 탐색을 접하다보니 굉장히 헷갈렸는데 해석학의 상한, 하한의 개념으로 생각하니 또 괜찮은 것 같다,,코드로 구현할 때만 헷갈리지 말자 ㅠㅠ! 매개변수 탐색 개념이 헷갈린다면 아래처럼 간단한 예시로 숫자를 삽입한다고 생각하고 이해해보는 것도 좋은 방법인 듯하다.

 

 

 

위 상황에서 10이라는 원소를 오름차순 정렬을 유지한 채로 삽입한다고 생각해보자.

가장 왼쪽에 삽입하기 위해서는 4번 index 위치에 10을 넣으면 된다. 그럼 원래 그 위치에 있던 수는 한칸씩 밀리게 되어 오름차순 정렬이 유지된다. 또한 가장 오른쪽 위치는 7번 index가 된다. 이렇게 가장 왼쪽 위치를 찾는 것이 lower_bound, 오른쪽 위치를 찾는 것이 upper_bound이다. 

 

수를 삽입한다는 개념 말고, 대소 관계 비교를 통해서도 lower과 upper bound에 대해 구분해보자.

lower_bound는 arr[i-1]< k <= arr[i]인 i를 찾는 함수이다. 즉, 원하는 조건인 arr[i] >= k 를 만족하는 많은 i 들 중에서 가장 작은 index를 찾고자 하는 것이다. 따라서 arr의 모든 값이 k 보다 작다면 배열의 마지막 다음 칸의 위치가 반환되어야 한다. 

위의 예시에서 k를 10이라 하면 3번 인덱스까지는 k보다 작지만, 4번 인덱스부터는 k와 같다. 즉 arr[i] >= 10을 만족하는 가장 작은 index는 4가 되는 것이다. 따라서 lower_bound(10)은 4가 된다.

 

upper_bound는 lower_bound와 반대로 arr[i-1] <= k < arr[i] 인 i를 찾는다. 즉 arr[i] > k 인 i의 최솟값을 반환하는 것이다. 마찬가지로 arr의 모든 원소가 k보다 작거나 같다면 arr의 마지막 다음 칸의 위치를 반환한다. arr[6] <= 10이지만 arr[7]> 10 이다. arr[i]>10을 만족하는 가장 작은 index가 7이므로 반환값은 7이 된다. 

 

즉, 원하는 값보다 크거나 같은 수가 나오는 가장 작은 index를 찾는 것이 lower_bound , 원하는 값보다 큰 값이 가장 먼저 나오는 가장 작은 index를 찾는 것이 upper bound이다. 

 

 

매개변수 탐색은 이분탐색과 초기 start와 end 값 설정에 차이가 있다. 배열의 index 범위 내에서만 결과값이 반환되는 이분탐색과 달리 매개변수 탐색은 주어진 배열의 모든 값이 조건을 충족하지 않을 때 맨 앞 또는 맨 뒤의 값이 반환될 수 있기 때문에 배열의 길이가 n이라면 end 값은 n-1이 아닌 n으로 설정되어야 한다.

 

또한 end가 0까지 감소할 수도 있기 때문에 start = -1이 되어야 한다. 이 말이 처음엔 이해가 잘 되지 않았는데, while문의 조건이 start+1 < end임을 생각해보면 이해할 수 있다.