이분 탐색(Binary Search)

이분 탐색 또한 앞서 포스팅 했던 Brute force와 마찬가지로 solved.ac의 Class2에서 등장하는 알고리즘이다.

이분 탐색은 문제를 푸는 하나의 도구로 굉장히 중요하며 자유자재로 사용할 수 있어야 한다. 먼 미래지만 세그먼트 트리를 형성할 때 이분 탐색과 비슷한 형식으로 트리를 형성하고 그리디(Greedy) 등의 알고리즘과 함께 나와도 이상하지 않을 정도로 사용 빈도가 꽤 높다. 

 

우리가 어떤 배열이나 벡터에서 숫자를 찾을 때 최악의 시간복잡도는 O(n)으로 선형 시간(Linear time)을 갖는다.                (** 알고리즘의 실행 시간이 데이터가 증가함에 따라 선형적으로 증가할 때의 시간을 선형시간이라고 함.)

하지만 이분 탐색의 시간복잡도는 log2(n)으로 선형 탐색에 비해 빠른 시간 안에 원하는 값을 찾아낼 수 있다.

 

다만 명심해야 할 것이 이분 탐색은 반드시 정렬된 데이터에서만 사용할 수 있다는 것이다. 이분 탐색 한번의 시간복잡도는 log2(n)이지만, 정렬하는데 NlogN의 시간복잡도가 소요된다. 따라서 최악의 경우 O(N)보다는 느리고 O(N^2)보다는 빠른 시간복잡도다. 백준 실버 2~골드정도 문제 기준으로 나이브 하게 풀어서 O(N^2)이상의 시간복잡도로 풀면 시간초과가 뜨는 문제들이 이분탐색을 사용하면 TLE를 피할 수 있는 경우가 있다.

 

다음 그림은 선형탐색과 이분탐색의 수행 과정을 나타낸 것이다.

 

 

Step의 개수를 비교하면 이분탐색이 훨씬 더 빠르다는 것을 한눈에 알 수 있다.

 

위의 그림을 예로 이분 탐색의 수행과정을 설명하면,

찾고 싶은 숫자가 target = 37이라고 하자. 그리고 배열의 첫 인덱스를 left = 0, 마지막 인덱스를 right = n-1이라고 하자. 그리고 중앙 인덱스를 mid = (left+right)/2 라고 하자. 여기까지는 이분 탐색을 하기 위한 세팅이다. 

<과정>

만약에 0. mid에 있는 값이 target(37)이라면 탐색을 종료.

만약에 1. mid에 있는 값 보다 target(37)이 더 크다면 왼쪽(left)를 mid+1로 옮긴다. left = mid+1.

만약에 2. mid에 있는 값 보다 target(37)이 더 작다면 오른쪽(right)를 mid-1로 옮긴다. right = mid-1.

 

위의 과정을 left < = right인 경우에 계속 수행해 준다. 만약 target을 찾지 못했다면 그 배열에 없다는 뜻이다.

과정을 이해하고 나면 왜 정렬된 데이터에서만 이분탐색을 사용해야 하는지 이해할 수 있을 것이다.

 

코드로는 다음과 같이 표현할 수 있다.

#include <iostream>
using namespace std;

int arr[17] = {1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
int BinarySearch(int target,int left,int right){
    while(left<=right){
        int mid = (left+right)/2;
        if(arr[mid] == target) return target;
        else if(arr[mid] > target) right = mid-1;
        else if(arr[mid] < target) left = mid+1;
    }
    return 0;
}

int main(){
    int left = 0;
    int right = sizeof(arr)/sizeof(int)-1;
    int target = 37;
    int ans = BinarySearch(target,left,right);
    cout << ans;
}

target을 찾기 위한 이분 탐색 코드이며, 기본적인 형태의 코드일뿐 필요에 따라 변형될 수 있으므로 응용문제를 많이 풀어보아야 한다.

 

 

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

1654번: 랜선 자르기

Class 2에 있는 이 문제는 이분 탐색의 개념 없이 들어가면 풀기 까다로운 문제다.

이분 탐색의 범위를 1~가장 긴 랜선으로 설정하고 이분 탐색을 진행해줘야 한다. mid의 길이로 랜선을 잘랐을 때 N보다 작으면 랜선이 더 짧아져야 하므로 right를 땡겨주고, N보다 크거나 같으면 만들 수 있는 랜선의 최대 길이를 구해야 하므로(길이를 더 길게 늘려도 되므로) 경계값을 찾기 위해 left를 mid로 땡겨주면서 탐색하면 된다.

 

 

 

코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
int main(){
    vector<ll> lan;
    ll n, k, length;
    cin >> k >> n;
    for(int i = 0 ; i < k; i++){
        cin >> length;
        lan.push_back(length);
    }

    ll start, end, mid, cnt;
    start = 1; end = *max_element(lan.begin(),lan.end());
    while(start <= end){
        cnt = 0;
        mid = (start+end)/2;
        for(auto v : lan){
            cnt += (v/mid);
        }
        if(cnt >= n) start = mid + 1;
        else end = mid - 1;
    }
    cout << end;
}

**랜선 길이가 int범위를 넘어가므로 long long으로 타입을 선언해야함.

 

이해가 어려우면 손으로 꼭 한번 써보면 좋다. 어차피 나중에 꽤 난이도 있는 문제들을 만나면 손으로 구상하는 연습도 필요하니 지금부터 바로 코드를 작성하기 보다는 손으로 쓰는 연습을 하고 코드를 한번에 짜는 것이 좋은 연습이 된다.

 

이 랜선 자르기 문제하고 똑같은 문제로 나무 자르기 문제도 있으니 복습용으로 꼭 한번 풀어보는 것을 추천한다.

그리고 Gold5에 용액 문제도 이분 탐색을 이용하면 충분히 고민하면 꽤 쉽게 풀 수 있는 좋은 문제이므로 풀어보시는 것을 추천한다.