파이썬 이분탐색 개념정리와 예제문제

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 7: PART 2. 알고리즘 유형 분석 - 이분탐색 Binary Search 37강 ~ 42강 내용 요약입니다.

 

1. 이진 탐색 Binary Search
1.1. 탐색 전에 반드시 정렬되어 있어야 한다.
1.2. 살펴보는 범위를 절반 씩 줄여가면서 답을 찾는다.
1.3. 정렬 O(NlogN) + 이진탐색 O(logN) => 결과적으로 O(NlogN)
1.4. 미리 정렬되어 들어오면 이진탐색만 하면 되므로 O(logN)
1.5.일차원 배열에서 탐색행위가 1회일때는 선형탐색이 유리하지만(O(N) < O(NlogN), 여러번 하는 경우에는 이진탐색이 유리하다.(O(N^2) > O(NlogN))

 

2. bisect_left/right 라이브러리

2.1. bisect_left([정렬된리스트], [찾을요소])

찾을 요소와 같거나 찾을 요소보다 더 큰 값이 처음으로 탐색되는 인덱스를 반환

2.1.1. 찾을 요소가 존재할 때

찾을 요소의 인덱스를 반환

2.1.2. 찾을 요소가 존재하지 않을 때

찾을 요소보다 더 큰 값이 처음으로 탐색되는 인덱스를 반환 (= 오름차순으로 들어갈 인덱스를 반환)

 

2.2. bisect_right([정렬된리스트], [찾을요소])

찾을 요소보다 큰 값들 중에서 처음으로 탐색되는 인덱스를 반환

2.2.1. 찾을 요소가 존재할 때

찾을 요소의 인덱스 + 1을 반환

2.2.2. 찾을 요소가 존재하지 않을 때

찾을 요소보다 더 큰 값이 처음으로 탐색되는 인덱스를 반환 (= 오름차순으로 들어갈 인덱스를 반환)

 

2.3. 사용 예 소스

from bisect import bisect_left, bisect_right

v = (0, 1, 3, 3, 6, 6, 6, 7, 8, 8, 9)
three = bisect_right(v, 3) - bisect_left(v, 3)
four = bisect_right(v, 4) - bisect_left(v, 4)
six = bisect_right(v, 6) - bisect_left(v, 6)

print(f'number of 3: {three}') # 2
print(f'number of 4: {four}') # 0
print(f'number of 6: {six}') # 3

 

3. 파라메트릭 서치
3.1. 최적화 문제를 결정 문제로 바꿔서 이진탐색으로 푸는 방법이다.
3.2. 최적화 문제 - 문제상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제
3.3. 결정 문제 - YES/NO Problem
3.4. 매개변수 Parameter가 주어지면 true or false가 결정되어야 한다.
3.5. 가능한 해의 영역이 연속적이어야 한다.
3.6. 범위를 반씩 줄여가면서 가운데 값이 true인지 false인지 구한다.
3.7. 이진탐색과 똑같은 원리

 

4. 예제문제

4.1. 예제문제(1) 

#boj.kr/2512 예산
#
N = int(input())
req = list(map(int, input().split()))
M = int(input())

lo = 0
hi = max(req)
mid = (lo + hi) // 2
ans = 0

def is_possible(mid):
    return sum(min(r, mid) for r in req) <= M

while lo <= hi:
    if is_possible(mid):
        lo = mid +1
        ans = mid
    else:
        hi = mid -1

    mid =(lo + hi) //2

print(ans)

4.2. 예제문제(2)

# boj.kr/10815 숫자 카드

from bisect import bisect_left, bisect_right

N = int(input())
cards = sorted(map(int, input().split()))
M = int(input())
qry = list(map(int, input().split()))
ans = []

for q in qry:
    l = bisect_left(cards, q)
    r = bisect_right(cards, q)
    ans.append(1 if r-l else 0)

print(' '.join(map(str, ans)))
#print(*ans)