[Python] bisect 모듈

백준에서 문제를 풀며 LIS(Longest Increasing Subsequence) 문제를 해결하다가 bisect모듈에 대해 알아보게 되었습니다. bisect 모듈은 Python 표준 라이브러리의 모듈로, 정렬된 리스트를 효율적으로 관리하는 데 사용합니다. 이 모듈은 리스트에 값을 넣거나 특정 값을 찾는 과정을 이분 탐색으로 수행하며, 시간 복잡도는 O(logn)입니다.

 

bisect 모듈의 주요 함수

1. bisect.bisect_left(list, value)

• 정렬된 list에서 value를 삽입할 수 있는 가장 왼쪽 위치를 반환합니다.
• 같은 값이 있는 경우, 해당 값의 가장 왼쪽 값의 위치를 반환합니다.

예시

import bisect

arr = [1, 2, 3, 5]
pos1 = bisect.bisect_left(arr, 4) # pos1 : 3
pos2 = bisect.bisect_left(arr, 2) # pos2 : 1

 

2. bisect.bisect_right(list, value) (= bisect.bisect)

• 정렬된 list에서 value를 삽입할 수 있는 가장 오른쪽 위치를 반환합니다.
• 같은 값이 있는 경우, 해당 값의 가장 오른쪽 값의 위치를 반환합니다.

예시는 위와 유사합니다.

 

3. bisect.insort_left(list, value)

• 정렬된 list에 value를 삽입하면서 리스트의 정렬 상태를 유지합니다.
• 값이 이미 존재하면 가장 왼쪽 위치에 삽입합니다.

예시

import bisect

arr = [1, 2, 3, 5]
bisect.insort_left(arr, 4)
print(arr) # arr = [1, 2, 3, 4, 5]

 

4. bisect.insort_right(list, value) (=bisect.insort)

• 정렬된 list에 value를 삽입하면서 리스트의 정렬 상태를 유지합니다.
• 값이 이미 존재하면 가장 오른쪽 위치에 삽입합니다.

예시는 위와 유사합니다.

 

참고

https://docs.python.org/ko/3.10/library/bisect.html

bisect — 배열 이진 분할 알고리즘 — Python 3.10.16 문서