하한과 상한
bisect_left와 bisect_right를 처음부터 구현한 다음, 대상 값의 첫 위치와 마지막 위치를 찾는 데 적용합니다.
하한과 상한은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
하한과 상한이란 무엇인가
정렬된 배열에서 대상값의 하한은 대상값보다 크거나 같은 첫 번째 요소의 인덱스입니다(보통 bisect_left라고 합니다). 상한은 대상값보다 엄격하게 큰 첫 번째 요소의 인덱스입니다(bisect_right). 이 둘을 함께 사용하면 대상값이 나타나는 모든 위치의 범위를 정하고 O(log n) 범위 질의를 수행할 수 있습니다.
이 두 연산은 면접 문제의 기반이 됩니다. 출현 횟수 세기, 범위 찾기, 삽입 위치 찾기 등에 활용됩니다.
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)하한 구현하기 (bisect_left)
bisect_left(arr, x)는 arr[i] >= x를 만족하는 가장 왼쪽 인덱스 i를 반환하며, 모든 요소가 더 작으면 len(arr)을 반환합니다. 구현에서는 상한을 배제하는 경계를 사용합니다. 즉 hi = len(arr)로 설정하고, 반복 조건은 lo < hi로 두며, arr[mid] >= x이면 hi = mid로 갱신합니다. 이렇게 하면 답이 가장 왼쪽의 유효한 위치로 수렴합니다.
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4상한 구현하기 (bisect_right)
bisect_right(arr, x)는 arr[i] > x를 만족하는 가장 왼쪽 인덱스 i를 반환합니다. bisect_left와 다른 줄은 하나뿐입니다. 조건이 arr[mid] < x에서 arr[mid] <= x로 바뀝니다. arr[mid] <= x이면 답은 mid의 오른쪽에만 있을 수 있으므로 lo = mid + 1로 설정하고, 그렇지 않으면 오른쪽에서 범위를 좁힙니다.
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5두 경계를 사용한 출현 횟수 세기
정렬된 배열에서 대상값의 출현 횟수를 O(log n)에 세려면 두 경계를 모두 적용합니다. 개수 = bisect_right(arr, target) - bisect_left(arr, target)입니다. 개수가 0이면 대상값이 없습니다. 이는 선형 순회보다 훨씬 빠르며 정렬된 데이터에 대한 빈도 질의의 표준적인 방법입니다.
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1대상값의 첫 번째 위치와 마지막 위치 찾기
LeetCode 34의 '정렬된 배열에서 요소의 첫 번째 위치와 마지막 위치 찾기'는 O(log n)에 [first_idx, last_idx]를 반환하는 문제입니다. 첫 번째 위치는 bisect_left(arr, target)이지만, arr[result] == target인 경우에만 유효합니다. 마지막 위치는 bisect_right(arr, target) - 1입니다. 어느 하나라도 확인에 실패하면 [-1, -1]을 반환합니다.
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]삽입 위치 (LeetCode 35)
LeetCode 35의 '삽입 위치 찾기'는 배열을 정렬된 상태로 유지하려면 대상값을 어디에 삽입해야 하는지 묻습니다. 이는 정확히 bisect_left(arr, target)입니다. 대상값이 존재하면 bisect_left가 해당 인덱스를 반환합니다. 존재하지 않으면 삽입될 인덱스를 반환합니다. 특별히 나눠 처리할 필요가 없습니다. 같은 함수가 두 상황을 모두 처리합니다.
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)bisect_left와 bisect_right의 차이
중복값이 없으면 bisect_left와 bisect_right는 같은 인덱스를 반환합니다. 차이는 대상값이 여러 번 나타날 때만 중요합니다. bisect_left는 첫 번째 값을 가리키고, bisect_right는 마지막 값의 바로 다음 위치를 가리킵니다. 기존 값 앞에 삽입할지(왼쪽), 기존 값 뒤에 삽입할지(오른쪽)에 따라 항상 적절한 함수를 선택하십시오.
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4정렬된 빈도 질의에 경계 적용하기
정렬된 배열에 대해 범위별 빈도 질의를 효율적으로 많이 처리해야 한다면 정렬된 배열을 한 번 미리 만들어 두고 각 질의에 이분 삽입 연산을 사용하십시오. 각 질의는 O(n)이 아니라 O(log n)에 '[lo, hi] 안에 몇 개의 요소가 있는가?'에 답할 수 있습니다. 정렬 후 값의 범위에 포함되는 요소를 세는 문제에서 자주 등장하는 방식입니다.
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)사용자 지정 키 이진 탐색
때로는 탐색 키가 저장된 값 자체가 아니라 그 값에서 파생된 속성일 수 있습니다. 파이썬의 bisect 모듈은 키 함수를 직접 지원하지 않지만, 반복문 안에서 키를 적용하여 직접 이진 탐색을 수행할 수 있습니다. 객체의 여러 속성 중 하나를 기준으로 목록을 탐색할 때 사용되는 방식입니다.
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]경계와 관련된 흔한 면접 오류
가장 흔한 실수는 bisect_left를 호출한 후 결과를 검증하지 않는 것입니다. 이 함수는 항상 유효한 삽입 인덱스를 반환하지만 해당 인덱스의 요소가 대상값과 같다는 보장은 하지 않습니다. 대상값을 찾았다고 가정하기 전에 항상 arr[result] == target을 확인하십시오.
두 번째 실수는 첫 번째 출현 위치를 원할 때 bisect_right를 사용하는 것입니다. bisect_right는 마지막 출현 위치의 바로 다음을 반환하므로, 여기서 1을 빼면 첫 번째가 아니라 마지막 위치를 얻게 됩니다.
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # Falsebisect_left와 bisect_right 중 무엇을 사용할지
다음이 필요할 때는 bisect_left를 사용하십시오. 대상값의 첫 번째 출현 위치, 기존 값을 오른쪽으로 밀어내는 삽입 위치, 또는 대상값의 존재 여부 확인입니다. 다음이 필요할 때는 bisect_right를 사용하십시오. 마지막 출현 위치의 바로 다음 위치, 기존 값이 모두 나온 뒤의 삽입 위치, 또는 대상값 이하인 요소의 개수입니다(이는 bisect_right(arr, target)와 같습니다).
둘 다 O(log n)에 실행되며 파이썬 표준 라이브러리의 일부이므로, 면접관이 처음부터 구현하라고 하지 않는 한 직접 가져와 사용할 수 있습니다.
빠른 확인
이 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
레슨 요약
이 레슨에서는 다음을 배웠습니다. bisect_left는 대상값보다 크거나 같은 첫 번째 요소를 찾습니다. bisect_right는 대상값보다 큰 첫 번째 요소를 찾으며, 이는 마지막 출현 위치의 바로 다음입니다. 또한 두 함수의 차이는 O(log n)에 출현 횟수를 알려 줍니다. 다음으로 배열 인덱스가 아니라 가능한 답의 범위를 탐색하는 정답 공간 이진 탐색을 살펴봅니다.
자주 묻는 질문
“하한과 상한” 강의는 무료인가요?
네 — “하한과 상한” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“하한과 상한”에서 뭘 배우나요?
bisect_left와 bisect_right를 처음부터 구현한 다음, 대상 값의 첫 위치와 마지막 위치를 찾는 데 적용합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“하한과 상한” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.