[Algorithm] Binary Search

Binary Search(이분탐색)은 정렬된 배열 안에서 특정한 값의 위치를 찾는 알고리즘이다. 

처음에 중간값을 임의의 값으로 설정하고 그 값과 찾고자 하는 값과 크고 작음을 비교해서, 

만일 임의의 값이 찾고자 하는 값보다 크다면 임의의 값을 최소값으로 해서 다시한번 중간값을 탐색하고, 

작다면 임의의 값을 최대값으로 해서 중간값을 탐색하게 하는 알고리즘이다.

 

정렬된 상태에서만 가능하다는 단점이 있지만, 정렬되어 있을 경우 이분 탐색이 선형 탐색을 할 때보다 더 나은 성능을 보장한다.

(선형 탐색의 경우 O(n)의 시간 복잡도를 가지는 반면에 이분 탐색의 경우 O(log n)의 시간 복잡도를 가진다.)

 

일반적인 이분 탐색은 위와 같지만 경우에 따라서 임의의 값을 최대값으로 할 지 최소값으로 할 지 결정해서 문제를 풀 면 된다.

 

 

가장 일반적이 이분 탐색의 경우 다음과 같이 해결하면 된다.

 

#include <stdio.h>
 
int A[10] = { 1, 5, 7, 15, 29, 33, 45 ,51 ,65, 69 };
 
int main(){
    int find = 65;
    
    int l = 0, r = 10, res = -1;
    while(l < r){
        int m = (l + r) / 2;
        if(A[m] < find){
            l = m + 1;
            res = m;
        }
        else r = m - 1;
    }
 
    printf("%d -> %d\n", find, res);
    return 0;
}

이를 좀 더 활용한 문제는 BOJ의 통나무 자르기(https://www.acmicpc.net/problem/1114)인데 이분 탐색을 실행 할 때

단순히 크기를 비교하는 것이 아니라 특정 조건을 만족하는지에 대해 확인 후 l, r값을 바꾸어주어야 한다.

이 문제에서는 통나무를 잘랐을 때 가장 긴 조각을 m으로 두고 그 길이에 대해서 C번 안에 자를 수 있는지를 계속 확인하면 된다.

 

이문제의 경우 풀이는 다음과 같다.

 

1. 입력으로 주어지는 통나무 자르는 위치에 0, L을 추가해준다

(통나무의 첫부분과 끝 부분도 잘라지는 위치로 생각하면 된다.)

 

2. 이분 탐색을 진행하기 위해서 정렬해 준다.

 

3. l(왼쪽 끝)을 0으로 r(오른쪽 끝)을 L이라 하고 이분 탘색을 시작한다

3.1. m(중간 값) = (l + r) / 2로 중간 값을 구한다. 이때, m은 통나무를 잘랐을 떼 가장 긴 조각의 길이이다.

 

3.2. m을 가장 긴 길이로 했을 때 통나무를 몇번 잘라야 하는 지 구하고, 마지막으로 남은 자투리가 m보다 큰 경우에는 

C(한계값)보다 큰 수를 반환해서 무조건 조건문에서 탈출하게 한다.

 

3.3. 만약 반환받은 자르는 횟수가 C보다 작거나 같다면 l = m + 1을 해서 가장 긴 조각이 더 긴 나무 조각을 탐색하게 하고

크다면 r = m - 1을 해서 가장 긴 조각이 더 작은 나무 조각을 탐색하게 한다.

 

4. 결과적으로 나온 res를 통해 나무를 잘랐을 때 다 자르지 않아도 되는 상황(<C)이 발생하면 자르는 위치를 1로 바꿔준다.

 

#include <stdio.h>
 
template <typename T>
void merge(T A[], int l, int m, int r){
    T* tmp = new T[r - l + 1];
    int lp = l, rp = m + 1, p = 0;
    while(lp <= m && rp <= r) tmp[p++] = A[lp] < A[rp] ? A[lp++] : A[rp++];
    while(lp <= m) tmp[p++] = A[lp++];
    while(rp <= r) tmp[p++] = A[rp++];
    for(int i = l; i <= r; i++) A[i] = tmp[i - l];
    delete[] tmp;
}
template <typename T>
void msort(T A[], int l, int r){
    if(r <= l) return;
    int m = (l + r) / 2;
    msort(A, l, m);
    msort(A, m + 1, r);
    merge(A, l, m, r);
}
 
int L, K, C;
int pos[10002];
int count(int len, int& cut) {
    int ret = 0, Sum = 0; cut = K;
    for (int i = K - 1; 0 <= i; i--) {
        Sum += (pos[i + 1] - pos[i]);
        if (len < Sum) { // 만들 수 없는 경우가 됨
            Sum = (pos[i + 1] - pos[i]);
            ret++;
            cut = i + 1;
            if (len < Sum) return C + 1;
        }
    }
    return ret;
}
int main() {
    scanf("%d %d %d", &L, &K, &C);
    for (int i = 1; i <= K; i++) 
        scanf("%d", pos + i);
    pos[0] = 0, pos[++K] = L;
    msort(pos, 0, K);
    int l = 0, r = L, res = L, cut;
    while (l <= r) {
        int m = (l + r) / 2; //m은 가장 긴 조각의 길이
        if (count(m, cut) <= C) {
            res = m;
            r = m - 1;
        }
        else l = m + 1;
    }
    if(count(res, cut) < C) cut = 1;
    printf("%d %d\n", res, pos[cut]);
    return 0;
}