이진 탐색과 매개변수 탐색

이진 탐색의 결론

5개월이라는 시간이 흐르면 자료구조/알고리즘 기억해 놨던게 사라지는 기현상이 있어서... 이진 탐색과 매개변수 탐색에 대해 이야기를 해보려고 한다. 사실 Binary Search는 구현 자체는 크게 어렵지도 않고, 개념적으로도 마찬가지로 어렵지도 않다. 업다운 게임을 생각해 보면 편한데, 1~100까지 수 중에 하나를 고르라 하면 50이 먼저 나올게 당연한 것 아닌가?

 

 

위대한 Gemeni님 께서도 친절하게 설명을 해 주신다.

마찬가지로 이진 탐색도 정렬되어 있는 수 중에서 (혹은 범위가 지정되어 있는 수 중에서) Up-Down 게임을 열심히 지지고 볶으면 된다. 물론 이진 탐색의 경우 수 중에서 "해당 값"이 반드시 존재하는 경우에 사용하고, 만약 "범위"로 검색하고 싶으면 매개변수 탐색이라는 것을 동원해야 한다.

 

#include <iostream>
#include <vector>

using namespace std;

bool det(vector<int>& array, int value) {
	// value가 조건에 만족하는가?
}

int binary_search(vector<int>& data){
    int first, last, mid;
    first = 0
    last = 1000000 // Maximum
    mid = (first + last)//2;
    
    while (firt <= last){
    	if (det(data, mid)) first = mid+1;
        else last = mid -1;
    }

 

대걍 이런식으로 되는 셈이다. 중간값 == 찾는 값 이라는 조건을 함수로 따로 넘겨서 특정 범위를 찾아오면 된다. 참 쉽죠?

 

근데 정작 문제를 보면 이야기가 달라지는게......

백준 2805번

사람은 문장을 5줄 이상 보면 뇌가 희미해지는 디버프가 붙는다. 일단 해당 문제는 반복문을 2번 돌리는 방식으로 풀어 볼 수 있겠으나 그러면 시간 복잡도가 O(N^2)가 되므로 참으로 끔찍하지 않을 수 없을 것이다. (10^12개 데이터를 1초 안에 처리해야 하는데, 뭐 이러쿵 저러쿵 해도 안될 것이다. 1.0Ghz CPU라 치고 IPC를 고려해서 계산해도... 코드를 또 기계어로 뱉어서 돌려야 하니 시간 초과는 뭐 안봐도 뻔한 셈.)

 

그래서 다른 방법을 찾아야 하는데.. 나무의 배열 자체는 정렬되어 있지 않으므로 이분 탐색을 쓸 수 없다. 근데 구해야할 답인 H는 범위가 정해져 있지 않은가? (20억->10억->5억->2억 5천 -> 1억 2천 오백 -> 6천 250만..... n번 계산 했다고 범위가 획기적으로 줄어든다!) 그래서 H를 일단 이분 탐색 돌리고, 이 H가 맞는지 매개변수로 어떻게 지지고 볶으면 O(NlogN)안에 끝내버릴 수 있다.

 

그래서 결론은 뭐냐면...

이진 탐색은 대게 정렬되어 있는 경우에만 사용 가능하다. 하지만 어떤 범위가 주어진 수가 특정 조건을 충족하는지 찾을 때도 사용할 수 있다! (이게 매개변수 탐색의 핵심이다.)

 

그리고 기억의 저 편으로 날라간 DS를 다시 공부해야겠구나 하는 결론도 든다.