Binary Search

이분 탐색에서 언제나 헷갈리는 경계값

 

lower_bound / upper_bound

lower_bound(k): k 이상의 수가 처음 등장하는 위치

upper_bound(k) : k 초과의 수가 처음 등장하는 위치

 

lower bound를 구하는 함수를 만들어보자

 

mid 위치의 값이 K와 같더라도, 왼쪽으로 범위를 줄인다.

더 앞쪽에 K 이상인 값이 존재할 수 있으므로

K 이상(≥ K)이 처음 등장하는 위치를 찾는 것이 목적

def lower_bound(N, arr, K):
    answer = N   # 못 찾으면 N (arr 끝 다음 위치)
    l = 0
    r = N - 1
    
    while l <= r:
        m = (l + r) // 2
        if arr[m] < K:
            l = m + 1
        else:
            answer = m
            r = m - 1
    
    return answer

 

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

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

 

while(left <= right)를 while(left < right)로 바꾸면?

완전히 다른 동작이 되고, lower_bound로서 정상적으로 작동하지 않는다.

왜냐하면 while l<=r 방식은

• 종료 조건: l == r+1
• 즉, 모든 후보 구간을 완전히 소진하고 나서 끝난다.
• 조건을 만족하는 최소 인덱스가 정확히 찾아짐.

이 방식의 반복 종료 후

• l은 조건을 만족하는 첫 번째 위치를 가리키고
• 이 때 저장형(answer = m)을 쓰면 더 안정적.

반면 while l<r 방식은

l<=r 와 다르게, 구간의 마지막 원소를 검사하지 않고 끝날 수도 있음.

 

예시

arr = [10, 20, 30, 40, 50], K = 50

lower_bound(50)은 index 4가 되어야 한다.

하지만 진행해보면

l	r	m	arr[m] < 50 ?	update
0	4	2	30 < 50	ㅣ = 3
3	4	3	40 < 50	ㅣ = 4

 

이때 l = 4 , r = 4 일 때

4 < 4 -> False 

arr[4]를 진행을 안하고 반복 종료 해버린다. 

즉, 마지막 인덱스를 아예 검사하지 못한 채 종료한다.

그래서 lower_bound 결과가 잘못되거나 미정 상태가 됨.

 

while l < r는 "구간의 크기를 1 이상으로 유지"하는 조건이다.

구간이 [4,4]처럼 원소 한 개가 되면 검사를 하지 못하고 종료한다.

하지만 lower_bound는 마지막 하나가 남은 순간에도 반드시 그 원소를 검사해야 한다.

 

이분 탐색에는 대표적으로 두 가지 구현 방식

① while l <= r + answer 저장 패턴

② while l < r + r = mid, l = mid + 1

 

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

l = 0
r = 1000000000000000001

while l <= r:
    mid = (l+r)//2
    people = sum(mid // time for time in times)

    if people < n:
        l = mid + 1       # mid는 ‘불가능’ 영역으로 확정
    else:
        r = mid - 1
     
answer = mid
return answer

이 로직으로 하면 끝나면 

• r : 조건을 만족하지 못하는 값들 중 가장 큰 값
• l : 조건(people >= n)을 만족하는 값들 중 가장 작은 값 (즉 우리가 찾는 최소 시간)

마지막에 계산된 mid는 “마지막으로 검사한 값”일 뿐이고 그 값이 조건을 만족하는지/안 하는지는 보장되지 않는다.

테스트를 돌려보면 mid 가 진짜 정답보다 1 작게 나오는 케이스들이 있다. 

그래서 이 패턴의 이분 탐색에서는 반복문이 끝난 뒤 l 을 반환해야 한다. 

def solution(n, times):
    l = 0
    r = 1000000000000000001

    while l <= r:
        mid = (l + r) // 2
        people = 0
        for time in times:
            people += mid // time

        if people < n:
            l = mid + 1
        else:
            r = mid - 1

    # 여기서 l이 우리가 찾는 최소 시간
    return l

 

Parametric Search

최적화 문제를 결정 문제로 바꾸어 푸는 방법

최적화문제: ~~를만족하는최적의답을구하시오(최소,최대

결정문제: OX문제,~~가조건을만족하는가?

 

이분탐색 parametric search를 할 때 고려해야 하는 요소

• 이분탐색이 가능한 문제인가? (특정값을 기준으로 YES/NO가 나뉘는가?)
• 답이 범위내에 “무조건” 존재하는 초기범위 L~R을 잡았는가?
• 구간의 중간점인 mid가 답에 포함되는가?
• 구간의 길이가 언제나1로 줄어드는가?

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

 

• 높이의 최댓값을 찾는 최적화 문제
• “높이 x에서 자르면 나무의 양이 충분한가?”의 결정 문제로 바꾸자
• 답은 무조건 [0,10억] 범위 내에 존재한다.
• 답이 [l,r]범위에 존재할때, 높이 (l+r)/2에서 자르면 충분한지 검사하여 구간을 절반으로 줄일 수 있다

N, M = map(int,input().split())
arr = list(map(int,input().split()))

l = 0
r = 1000000000
while l < r :
	m = (l+r+1)//2
    
    sum = 0
    for h in arr:
    	if h > m : sum += h-m
        
    if sum >= M: l = m
    else: r = m-1
    
print(l)

 

 

 

출처: Future Tech Academy