[알고리즘] 이분탐색 헷갈리지 않기

저는 이분탐색 문제를 풀 때마다 헷갈립니다. .

탈출 조건 중 어느 걸 선택해야 할지, while 문도 범위를 매번 정확히 하지 않은채 문제를 풀곤 했는데요.

오늘 헷갈리지 않게 구현하는 방법을 정리하려고 합니다 !

이분탐색

결정 문제의 답이 이분적일 때 사용할 수 있는 탐색 기법입니다.

이 때, 결정 문제란 답이 Yes or No인 문제를 말합니다.

 

예를 들어, 1 ~ 50까지의 오름차순 정렬된 카드 더미(v[])에서 val번 카드를 찾는 문제를 예시로 들게요.

이 경우, 결정 문제를 "v[i] >= val인가 ?"로 잡으면 결정 문제는 i가 증가함에 따라 F, F, ... F, T, T, ... 와 같이 분포하게 됩니다.

이 때, 찾고자 하는 값은 처음으로 v[i] >= val인 지점, 즉 처음 결정 문제가 T가 되는 i값입니다.

이렇게 문제의 답이 달라지는 경계를 찾을 수 있습니다.

 

이분 탐색의 아이디어는 경계를 포함하는 구간 [low, high]를 잡은 뒤 구간의 길이를 절반씩 줄여나가며 low, high이 경계 지점에 위치하도록 하는 것입니다.

이분 탐색이 끝나면 low의 다음칸은 high이며 Check(low) != Check(high)입니다.

이 때, Check(x)는 결정 문제의 parameter가 x일 때 결정 문제의 답을 의미합니다.

 

위의 예시의 경우 [1, 50] → [25, 50] → ... → [27, 28] 로 low, high를 줄여나간뒤 high = 28을 찾아주면 됩니다.

이분 탐색은 구간의 범위가 클 때 효과적입니다.

범위를 반으로 줄여가며 탐색하여 O(logN)의 시간복잡도를 가지기 때문이죠.

문제풀이

구현 방법은 건너뛰고, 실제 문제를 풀며 경계와 범위에 대해 생각해봅시다.

프로그래머스 입국심사 문제입니다.

 

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n	times	return
6	[7, 10]	28

 

일단 문제를 간단히 설명해볼게요.

입국심사를 기다리는 사람 n이 주어지고, 각각 심사관이 한 명을 심사하는데 걸리는 시간이 배열로 주어집니다.

이 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하는 문제입니다.

 

음, 일단 제한사항을 보면 n의 범위가 무려 10^9이고 .. 걸리는 시간의 범위도 10^9입니다.

O(N)도 시간 초과가 날 것으로 보이므로 단번에 이분탐색을 떠올릴 수 있어야합니다.

 

그럼 어떻게 이분탐색을 구현할까요 ?

1. 먼저 low와 high를 잡아야합니다.

   low = 0 / high = times 중 가장 큰 값 * n

   이 문제에서 Check(low) = F 이고, Check(high) = T 입니다.

2. Check(mid) 라면 high = mid 아니라면 low = mid를 반복

    이 때, Check란 결정 문제로 이 문제에서는 "total += times[i] / mid가 n 이상의 사람을 심사할 수 있는가?"가 되겠네요.

3. low + 1 == high가 되면 탈출합니다. low와 high는 경계에 위치하게 되겠죠.

    이 문제에서는 정답의 분포가[F ~ T]입니다. 그러므로 정답은 정답의 경계 중 high가 되겠죠.

 

[전체 코드]

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var low = 0
    var high = times.sorted().last! * n
    
    func check(_ mid: Int) -> Bool {
        var total = 0
        
        for time in times {
            total += (mid / time)
        }
        
        return total >= n
    }
    
    while low + 1 < high {
        let mid = (low + high) / 2
        
        if check(mid) {
            high = mid
        } else {
            low = mid
        }
    }
    
    return Int64(high)
}

주의 사항

1. low와 high는 항상 정답 범위를 나타낼 수 있도록 정하기

2. 오버플로우에 주의

3. 결정 문제라는 걸 명심하여 Check 함수 구현하기

 

원래 풀던 방식과 달리 확실하게 경계에 대한 이해와 low와 high 설정이 쉬워졌습니다 . .

미리 알았다면 얼마나 좋았을까 . . 하지만 지금이라도 확실히 알고 넘어갈 수 있어서 행복하네요 하하

빨리 이분탐색 문제 하나 더 풀러 가봐야겠습니다 . . 홧팅

---

참고

https://www.acmicpc.net/blog/view/109