이분 탐색

👣 개요

쉽게 말해서 정답을 찍는 방법이다.
다만, 스무 고개 처럼 범위를 점차 줄여가며 찍는 범위를 점차 줄여가는 방법이다.
보통 문제를 직접 풀 수가 없지만 정답값이 주어졌을 때,
해당 값이 정답인지 아닌지 확인하기 더 수월할 때, 사용한다.

 

👣 복잡도

	평균
Big O 표기법	O(log n)

 

👣 알고리즘 절차

1. 시작점과 끝점을 설정합니다.
2. 시작점과 끝점을 이용하여 중간점을 계산합니다. 중간점은 (시작점 + 끝점) // 2로 구할 수 있습니다.
3. 중간점의 값과 찾고자 하는 값과 비교합니다.
   
   • 중간점의 값이 찾고자 하는 값보다 크면, 찾고자 하는 값은
     중간점의 왼쪽에 위치하므로 끝점을 중간점의 이전 인덱스로 업데이트합니다.
   • 중간점의 값이 찾고자 하는 값보다 작으면, 찾고자 하는 값은
     중간점의 오른쪽에 위치하므로 시작점을 중간점의 다음 인덱스로 업데이트합니다.
4. 시작점과 끝점이 같아질 때까지 2번부터 3번까지의 과정을 반복합니다.
   • 시작점이 끝점보다 커지면 찾고자 하는 값이 배열이나 리스트에 존재하지 않는 경우이므로 탐색 실패로 처리합니다.

s,e = 1,10e18
while e-s > 1:
    m = (e+s) // 2
    s,e = (s,m) if verify(m) else (m,e)

 

👣 적용 예시

위 문제는 프로그래머스의 '입국 심사' 문제다.

프로그래머스

위 문제는 "n명의 사람이 심사를 받는 최소 시간"을 계산하는 문제다.
하지만 그대로 풀기엔 고려사항이 너무 많고 꽤 복잡하다

하지만 이분 탐색을 풀기 위해 문제를 살짝 비틀면
"T 시간동안 n명의 사람이 심사를 받을 수 있는가?"라는 문제로 바꿔볼 수도 있다.

두 문제를 비교하면 후자의 질문이 훨씬 해결하기 쉽다.
각 심사관 마다 "T // [심사관의 인당 처리 시간]" 값의 합산을 한 것이 T 시간 동안 처리한 입국 심사 처리 건수이기에
T 시간동안 n명의 사람이 심사를 받을 수 있는가? 는 다음 함수로 간단히 판단할 수 있다.

verify = lambda time: sum(time//i for i in times) >= n

특정 시간에 수렴할 수 있도록 반절씩 범위를 좁혀나가면 끝내 두 포인터의 간격이 1인 상황이 찾아온다.
그 때, 왼쪽 포인터는 False, 오른쪽 포인터는 True가 되며 False와 True의 경계값을 알 수 있게 된다.
이로서 "n명의 사람이 심사를 받는 최소 시간"을 계산할 수 있게 된다.

def solution(n, times):
    verify = lambda time: sum(time//i for i in times) >= n
    
    s,e = 1,10e18
    while e-s>1:
        m = (e+s)//2
        s,e = (s,m) if verify(m) else (m,e)
    return e

결국 위와 같이 이분 탐색으로 문제를 해결할 수 있게 된다.