[알고리즘] 이분 탐색과 최적화 문제

참고글

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

이분 탐색 (Binary Search)

검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘. 보통은 정렬이나 탐색을 공부할 때 처음 배운다. 내가 원하는 수가 어디에 있는지, 가장 큰 범위에서 반씩 줄여가며 찾아낸다. 그런데 이런 이분 탐색은 결정 문제(Decision Problem, 어떤 형식 체계에서 예-아니오 답이 있는 질문)의 답이 이분적일 때, 이분적인 그 경계값을 찾을 때 사용할 수 있다.

그리고 우리는 이 점을 활용하여 문제의 최적값을 구하는 데도 사용할 수 있다. 아래의 문제를 보자.

프로그래머스 43238. 입국심사

문제: https://school.programmers.co.kr/learn/courses/30/lessons/43238

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 찾는 문제이다. 이 문제 자체는 결정 문제라고 할 수 없다. 답이 이분적이지 않기 때문이다. 그래서 우리는 이 최적화 문제를 결정 문제로 바꿔줘야 한다.

모든 사람이 심사를 받는데 걸리는 최소 시간 M.
M = 모든 사람이 검사를 받은 상태인 시간들 중 최솟값.

M은 모든 사람이 검사를 받지 않은 범위인 [0, M)과 모든 사람이 검사를 받은 상태인 [M, INF) 범위의 경계점이다.

즉, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 찾는 문제에서 m시간 뒤에는 모든 사람이 심사를 받은 상태인가? 를 확인하는 결정 문제가 된다. 우리는 이 결정 문제의 경계값인 m을 찾아주면 되는 것이다.

 

위의 문제의 구현을 간단히 작성해 보면,

main(){
    while(lo+1 < hi){
        mid = (lo + hi) / 2;
        if (check(mid) == check(lo)) lo = mid;
        else	hi = mid;
    }

    // lo(==mid)+1 == hi가 되었을 때   * check(lo)와 check(hi)는 반드시 다르다 *
    // 문제가 최댓값을 묻는 경우, 범위의 최댓값은 경계의 왼쪽에 있으므로 lo를 선택
    // 문제가 최솟값을 묻는 경우, 범위의 최솟값은 경계의 오른쪽에 있으므로 hi를 선택
    return hi;
}

check(int m){
    // 각 심사대에서 m시간 내에 최대한 사람을 받음.
    // 각 심사대에서 받은 사람의 합이 전체 인원보다 적으면 false, 같거나 많으면 true
}

이렇게 된다.

이분 탐색의 구현은 최상단의 백준 게시글을 참고하면 된다.