[알고리즘] 이진 탐색 심화(lower bound, upper bound)

이번엔 이진탐색의 심화인 upper bound, lower bound에 대해 배워보겠습니다.

이진탐색에 대하여 정확히 알고싶으신 분, 결정값에 모르시는 분, 리턴 값에 lo를 쓰는 지에 대하여 모르시는 분에게 적합할 것 같습니다.

 

 

 

이진 탐색의 기본 원리는 다음과 같습니다.

- L[mid] == target  ▶ return mid

- L[mid] < target  ▶ hi = mid - 1

- L[mid] > target  ▶ lo = mid +1

 

하지만 이것만으로 이진탐색 문제들을 풀 수 없습니다. Lower bound와 Upper bound에 대하여 알아 보겠습니다. lo는 가능한 값들 중 최소값, hi는 가능한 값들 중 최대값을 의미합니다.

Lower bound

해당 값 이상의 값이 처음 나오는 인덱스 반환

 

LOWER BOUND

def lower_bound(lo,hi,target):
    while lo<=hi:
        m = (lo+hi)//2
        if L[m] < target:
            lo = m +1
        else:
            hi = m-1
    return lo

 

 

Upper bound

해당 값보다 큰 값이 처음 나오는 인덱스 반환

 

UPPER BOUND

def upper_bound(lo,hi,target):
    while lo<=hi:
        m = (lo+hi)//2
        if L[m] <= target:
            lo = m +1
        else:
            hi = m-1
    return lo

 

 

 

Decision Problem

출처 : wikipedia

어떤 문제에 대하여 예 or 아니오로 나오는 문제를 말합니다

 

 

Decision Problem과 lower bound, upper bound을 활용하여 문제를 해결 할 수 있습니다.

 

예시로는 다음과 같습니다.

ex) 어떤 조건을 만족하는 최소값을 구하여라.

ex) 어떤 조건을 만족하는 최대값을 구하여라.

 

실전 문제를 하나 같이 풀어보겠습니다.

 

 

백준 2110번  공유기 설치 python

2110번: 공유기 설치

• 거리를 기준으로 했을 때 공유기 개수를 이용하여 이진탐색 실행
• 가장짧은 거리 : 0 , 가장 긴 거리 : houses[-1]

min_d,max_d = 0,houses[-1]

• 중간 거리를 이용하여 공유기 개수 체크
• 최근에 공유기가 설치된 집을 기준으로 거리이상 차이날 시 공유기 추가

def check(houses,distance):
    current = houses[0] 
    cnt = 1
    for house in houses:
        if house - current >= distance:
            cnt+=1
            current = house
    return cnt

• 현재 거리를 기준으로 공유기 개수가 같거나 많을 경우 거리를 늘림(공유기 개수를 줄이기 위해)
• 개수가 적을 경우 거리를 줄여야 함(공유기 개수를 늘리기 위해)

if check(houses,d)>=C: # 공유기 개수가 같거나 많을 시 거리를 늘려야 함
        ans = d
        min_d=d+1
else: # 공유기 개수가 작을 시 거리를 줄여야함
    max_d = d-1

전체코드

def check(houses,distance):
    current = houses[0] 
    cnt = 1
    for house in houses:
        if house - current >= distance:
            cnt+=1
            current = house
    return cnt

import sys
input = sys.stdin.readline
N, C = map(int,input().split())
houses = [int(input()) for _ in range(N)]
houses.sort()
min_d,max_d = 0,houses[-1]
while min_d<=max_d:
    d = (min_d+max_d)//2
    if check(houses,d)>=C: # 공유기 개수가 같거나 많을 시 거리를 늘려야 함
        ans = d
        min_d=d+1
    else: # 공유기 개수가 작을 시 거리를 줄여야함
        max_d = d-1
print(ans)