Binary Search

고민의 시작

---

근래 들어 PS 지식이 부족함을 느꼈다.

특히 이진 탐색에 굉장히 약하다고 느꼈는데, 아무래도 동작 방식을 너무 두루뭉실하게 알고 있던게 아닐까 생각한다.

 

 

 

 

 

 

왜 이 고민이 필요해?

---

• 명확한 동작방식을 이해하고, binary_search를 응용한 문제를 통해 문제해결을 명확하게 하고자 한다.
• 이후, 파이썬에서는 bisect라는 라이브러리를 제공하는데 이에 내부 구현을 살펴보고, 구현 및 응용을 해보고자 한다.

 

 

 

 

 

Binary Search란?

---

• 이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

동작 원리

1. 현재 데이터 셋의 중앙값을 선택한다
2. 중앙값 > 타깃 데이터 일 때 중앙값 기준으로 왼쪽 데이터 셋을 선택한다
3. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료

 

이렇게 이진탐색을 사용하면 N개의 데이터에서 logN번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.

예를 들어, 16개의 데이터면 최대 4번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.

다만 이진탐색은 데이터가 정렬되어 있어야 한다.

 

 

 

 

 

 

 

 

Bisect

---

주요 함수

bisect.bisect_left(a, x, lo=0, hi=len(a))

• 리스트 a에 x를 삽입할 수 있는 가장 왼쪽 인덱스를 반환
• a는 정렬되어 있어야 한다

bisect.bisect_right(a, x, lo=0, hi=len(a)) 또는 bisect.bisect(a,x)

• 리스트 a에 값 x를 삽입할 수 있는 가장 오른쪽 인덱스를 반환

bisect.insort_left(a, x, lo=0, hi=len(a))

• x는 a에 정렬된 상태를 유지하며 왼쪽에 삽입

bisect.insort_right(a,x, lo=0, hi=len(a)) 또는 bisect.insort(a,x)

• x를 a에 정렬된 상태를 유지하며, 오른쪽에 삽입

 

 

사용 예시

import bisect

a = [1,3,4,7]

# bisect_left
idx = bisect.bisect_left(a,4)
print(idx) # 2

# bisect_right
idx = bisect.bisect_left(a,4)
print(idx) # 2

# insort_left
bisect.insort_left(a,2)
print(a) # [1, 2, 3, 4, 7]

# insort_right
bisect.insort_right(a,4)
print(a) # [1, 2, 3, 4, 4, 7]

결과

2
2
[1, 2, 3, 4, 7]
[1, 2, 3, 4, 4, 7]

 

 

 

 

내부 동작 방식

(bisect_left 구현)

def bisect_left(a,x, lo=0, hi=None):
    """x를 정렬된 리스트 a에 삽입할 수 있는 가장 왼쪽 인덱스를 반환"""

    if lo < 0:
        raise ValueError('lo must be non-negative')

    if hi is None:
        hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1

        else:
            hi = mid

    return lo

a = [1, 3, 4, 4, 4, 4, 7]

print(bisect_left(a, 4))    # 2

 

 

 

(bisect_right 구현)

def bisect_right(a, x, lo=0, hi=None):
    """x를 정렬된 리스트 a에 삽입할 수 있는 가장 오른쪽 인덱스 반환"""

    if lo < 0:
        raise ValueError('lo muse be non-negative')

    if hi is None:
        hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2

        if a[mid] <= x:
            lo = mid + 1

        else:
            hi = mid

    return lo

a = [1, 3, 4, 4, 4, 4, 7]
print(bisect_right(a, 4))   # 6

 

 

 

(insort_left 구현)

from bisect import bisect_left
def insort_left(a, x, lo=0, hi=None):

    """x를 a에 정렬을 유지하면서 가장 왼쪽에 삽입"""
    i = bisect_left(a,x,lo,hi)
    a.insert(i,x)

a = [1, 3, 4, 7]
insort_left(a, 2)
print(a) # [1, 2, 3, 4, 7]

 

 

 

 

(insort_right 구현)

from bisect import bisect_right

def insort_right(a,x,lo=0, hi=None):
    """x를 a에 정렬을 유지하면서 가장 왼쪽에 삽입"""
    i = bisect_right(a,x)
    a.insert(i,x)

a = [1, 3, 4, 7]

insort_right(a, 2)
print(a)                    # [1, 2, 3, 4, 7]

 

 

 

간단한 문제 풀이

---

• https://www.acmicpc.net/problem/2343

풀이 과정

1

• 이진 탐색의 시작 인덱스는 최대 길이의 레슨이고 종료 인덱스는 모든 레슨 길이의 합
• 총 9개로 구성된 레슨의 시간은 각각 1, 2, 3, 4, 5, 6, 7, 8, 9 이므로 이진탐색의 시작 인덱스는 최대 레슨 시간인 9, 종료 인덱스는 레슨 시간을 모두 합한 45이다.
• 불루레이 개수가 3개일 때, 9~ 45에서 블루레이 크기의 최솟값을 이진 탐색으로 찾으면 됌

2

• 9 ~ 45 사이에서 이진 탐색
• 시작 인덱스 > 종료 인덱스 일때 까지 수행

 

import sys
input = sys.stdin.readline

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

start = max(S)
end = sum(S)
while start <= end: # 주의!! start < end의 경우, 정답을 찾고 더 나은 답을 찾으려고 할때 아닌경우 다시 못돌아오게 됌
    mid = (start + end)//2
    sum_value = 0
    count = 0
    for i in range(N):

        if sum_value + S[i] > mid:

            sum_value = 0
            count += 1

        sum_value += S[i]

    if sum_value != 0:
        count += 1

    if count > M:
        start = mid + 1

    else:
        end = mid - 1

print(start)

 

 

고찰

---

• 위 문제에서 이분탐색의 한 종류인 Parametric Search를 모르고 있었던것 같다.

 

 

항목	이분 탐색 (Binary Search)	Parametric Search (파라메트릭 서치)
목적	정확한 값/인덱스 찾기	조건을 만족하는 최솟값/최댓값 찾기
탐색 대상	배열의 값 or 인덱스	특정 수 범위 (예: 용량, 비용 등)
사용 조건	값이 정렬돼 있어야 함	값의 범위에 대해 조건 함수가 단조적이어야 함
종료 조건	정확히 일치하는 값/인덱스	가능한 값 중 가장 작은/큰 것
반복 구조	while lo < hi: 또는 while lo <= hi:	보통 while lo <= hi:
대표 예	bisect_left, index of target	블루레이 나누기, 예산 배정, 공유기 설치

 

 

 

이분탐색은 정확한 위치 / 값을 찾는 과정이고,

Parametric Search는 조건을 만족하는 최적의 값을 찾는 과정이다.

 

 

좀 명확한 풀이 방식을 알고 진행해야겠다고 생각했다

 

 

 

마지막으로 Parametric Search 문제 추천하면서 떠나겠습니다.

 

2343 - 기타 레슨	강의들을 M개 블루레이로 나눌 때, 최소 블루레이 크기
1654 - 랜선 자르기	K개의 랜선으로 N개를 만들 수 있는 최대 길이
2512 - 예산	총액을 넘지 않으면서 각 지자체에 분배할 수 있는 최대 요청 상한선
2110 - 공유기 설치	집들에 공유기 N개를 설치할 때, 공유기 간 최소 거리의 최댓값
2805 - 나무 자르기	H 높이로 나무를 잘라 얻을 수 있는 최대 톱날 높이