이진탐색(Binary Search)와 Parametric Search

이진탐색(Binary Search)와 Parametric Search

1. 이진탐색

1.1 기본 아이디어

우리가 원하는 값을 찾고 싶을 때에는 정말 간단하게 생각하면, 모든 값들을 하나씩 보면서 맞는지 아닌지 확인는 방법이 직관적인 방법이라고 할 수 있다. 하지만 이렇게 찾는 것은 가장 마지막에 원하는 값이 있을 경우, 모든 값 들을 한번 씩 살펴보아야 하기 때문에, O(N)으로 볼 수 있다. 그렇다면 좀더 효율적인 방법은 없을까? 에서 시작한 것이 바로 이진탐색(Binary search)이다. 

이진탐색(Binary search)의 경우는 결과적으로 보면 O(logN) 만에 원하는 값을 찾을 수 있는데, 그 이유는 정렬이 되있다는 가정이 있기 때문이다.  아래의 그림을 보면서, 왜 그러한지 직관적으로 이해를 하면 좋을 것 같다.

그림에 대해 간단하게 설명을 덧붙여보면,

나는 3이 어디있는지를 찾고 싶다. 

-> 가운데를 찾아봤다. 

-> 3보다 큰값이다. 

-> 정렬이 되어 있으니깐 5보다는 작은 값들중에서 있을 것이다.

== 5보다 큰 것들은 더이상 관심이 없다.

이러한 과정을 반복하게 된다.ㅜ

즉 한번 할 때 마다 가운데 값을 기준으로 비교를 해 나가면서, 비교의 범위를 절반 씩 줄여 나갈수 있게 된다.

한번 할 때마다 범위가 절반 씩 줄어들기 때문에 직관적으로 O(logN)이라는 것을 이해 할 수 있을 것이다.

1.2 구현

이미 눈치가 빠른사람은 알겠지만, 기본적으로 재귀로 구현을 떠올리기 쉽다.  재귀가 가능하니 역시 반복문으로 가능하다.

본인은 재귀의 경우 구현은 쉽지만, 성능과 디버깅의 경우 어려움을 많이 겪었기 때문에 반복문으로 구현을 하였다.

#include <cstdio>
 
int bSearch(int *arr,int size, int value) {
 
    int left = 0;
    int right = size - 1;
    int mid;
 
    while (left<right) {
        mid = (left + right) / 2;
        if (arr[mid] == value) return mid;
        else if (arr[mid] > value) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}
 
 
int main() {
    int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
    printf("%d에 %d가 존재합니다.\n", bSearch(arr,10,3),3);
    printf("%d에 %d가 존재합니다.\n", bSearch(arr, 10, 100), 100);
    return 0;
}

가장 기본적인 구현 형태로, 값이 존재하면 위치한 인덱스를 반환하고, 존재하지 않다면 -1을 반환하는 코드이다.

존재한지 않는 경우 가장 비슷한 작은값을 반환을 해주는 경우나,

또는 가장 비슷한 큰값을 반환해 주는 경우로 코딩을 할 수도 있다.

재귀로 구현하는 것은 직접 구현해보길 바란다.

2. Parametric Search

2.1 기본 아이디어

Parametric Search의 경우는 Binary Search의 응용한 느낌으로, 기본적인 탐색 방법은 Binary Search와 일맥상통하다.

그런데, Binary Search의 경우는 위에서 본것과 마찬가지로, 나의 배열의 값들을 기준으로 존재하는지 존재하지 않는지에 대해서 찾는 과정이였다면, 내가 원하는 실수의 정답의 범위에서 이진탐색을 진행한다고 보면 된다.

위의 그림처럼 무언가 배열의 들어가 있는 값이 아닌, 수직선 상 위에서 내가 원하는 값을 이진탐색으로 찾아가는 느낌으로 이해하는 것이 좋을 것 같다.

여기서 또 한가지, 이진탐색과는 달라지는 점이있다. 바로 비교함수이다.

위에서 기본적인 이진탐색의 방법에 대해서 살펴보았는데 다시한번 살펴보면, 이진탐색의 경우에는 Mid의 값이 내가 찾는 값인지 아닌지가 중요하게 된다. 즉 일치여부가 중요하게 된다.

기본적인 틀 자체는 똑같지만, Parametric Search의 경우에는 그것과는 약간 달리 주로 내가 원하는 조건을 만족하는 가장 알맞는 값을 특정한 오차범위 이내에서 알고싶어 할 때 사용할 경우가 많다. 물론 오차범위가 없는 경우도 존재한다.

핵심은 바로 내가 원하는 조건을 만족하는 가장 알맞는 값을 찾는 것이다.

간단한 예를 들어보면, 방정식을 푼다고 생각해 보자.

Y= X^4+X^3+X^2+X 라는 방정식의 Y값이 주어졌을 때 0~10 사이에 값중 알맞는 것을 소수점 5자리 이내의 오차범위에서 구해보자고 하자. 수학적으로 풀수 있는 방법이 있다 할지라도 Parametric search를 배웠으니 이용해보자.

Y= 15가 주어졌다고 생각해보자. 

아래의 그림으로 설명하겠다.

내가 원하는 값을 찾아서 이 경우에는 값이 클 경우 범위를 줄여가면서 계속 탐색을 하게 된다.

실제 이과정을 통해서 몇번만 더 진행을 하게 되면 상당히 답에 근접한 값을 얻을 수 있게된다.

즉, 기본 아이디어를 간단하게 다시 정리를 하면!

- 이진탐색과 기본적으로 같다.

- 내가 가지고 있는 값이 아닌 값의 범위를 기준으로 답을 탐색한다.

- 그러기 위해서는 답에 가까워 질수 있게 만드는 compare 함수를 적절히 만들어야 한다.

2.2 구현

사실 parametric search의 경우는 일반적인 구현이라고 할 것이 없이 상황에 맞게, 문제에 알맞게 짜는 것이 중요하다고 본다.

아래의 소스는 실제 문제풀이를 할 때 만들었던 소스이므로 참고만 하길 바란다.

백준저지의 2343번 문제를 풀때 사용했던 소스이다.

#include<cstdio>
#include<vector>
#include<algorithm>
#define MAX 100000000
using namespace std;
 
int cmp(int length, int partN, vector<int>& les)
{
    int tot = 0;
    int partial = 0;
    int cnt = 1;
    int i;
    for (i = 0; i < les.size();i++) {
        if (partial + les[i] > length)
        {
            if (les[i] > length) return 0;
            partial = les[i];
            cnt++;
        }
        else partial += les[i];
    }
    if (partN >= cnt) return 1; //length로 partN개 가능
    else return 0; //length가 너무 작음
}
 
 
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    vector<int> lesson(N);
    for (int i = 0; i < N; i++) scanf("%d", &lesson[i]);
    
 
    int left = 0;
    int right = MAX;
    int mid;
    int min = 1 << 30;
 
    while (left<=right) {
        mid = (left + right) / 2;
        //조건을 만족할 경우 -> 더 작은 것을 찾아본다.
        int condition = cmp(mid, M,lesson);        
        if(condition==1){
            min = (min < mid) ? min : mid;
            right = mid - 1;
        }
        //블루레이 시간이 너무 짧아서 mid를 넓힌다.
        else
        {
            left = mid + 1;
        }
    }
    printf("%d\n", min);
    
    
 
 
    return 0;
}