[Python] 이진 탐색 알고리즘이 담겨있는 모듈 bisect 알아보기

선형 탐색 vs 이진 탐색

뭔가를 찾아야 할 때, '처음부터 하나하나 다 찾아보기 vs 필요 없는 거 반씩 거르면서 찾기' 둘 중에 뭘 고르겠냐고 하면 닥 두 번째다.

전자는 선형 탐색, 후자는 이진 탐색으로 시간 복잡도가 각각 O(N), O(logN)이다.

이진 탐색은 중간 지점의 값이 찾아야 할 값보다 작다면 오른쪽 반절을, 크다면 왼쪽 반절을 보면서 반씩 줄여나가며 원하는 값을 찾아내는 알고리즘이다.

 

* 탐색에 대한 이해가 조금 부족하시다면 아래의 글을 참고해주세요!

2022.12.05 - [Algorithm/Algorithm] - [알고리즘] 파이썬으로 이진 탐색(Binary Search) 구현하기

[알고리즘] 파이썬으로 이진 탐색(Binary Search) 구현하기

 

시간복잡도가 이진 탐색이 더 좋다는 것은 알겠지만 이진 탐색 코드를 매번 구현하는 것은 조금 귀찮다. 파이썬에는 이진 탐색을 간편하게 이용할 수 있도록 bisect라는 모듈이 존재한다. 이번 포스팅에서는 bisect에 대해 알아보려고 한다.

 

bisect 모듈 사용법

- import 해오기

모듈이므로 import해서 불러올 수 있다.

import bisect

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

리스트 a에서 원소 x에 대한 삽입점을 찾는다. 매개변수 lo, hi는 리스트 인덱스의 최소값과 최대값이다. 기본값으로 리스트 전체를 가리키게 설정되어 있으며 기본값 그대로 사용할 경우에는 생략 가능하다.

예를 들어서 num = [0, 1, 2, 3, 4, 5]에 3을 삽입하고 싶다면 어떤 인덱스에 삽입하면 될지를 알려준다.

nums = [0, 1, 2, 3, 4, 5]
print(bisect.bisect_left(nums, 3)) # 3

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

left와 유사하지만 a 안에 x와 동일한 값이 이미 존재한다면 그 뒤에 있는 삽입점을 반환한다.

nums = [0, 1, 2, 3, 4, 5]
print(bisect.bisect_right(nums, 3)) # 4

이미 3이 존재하므로 3의 뒤에 있는 삽입점 인덱스 4를 반환해주는 것을 볼 수 있다.

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

이미 정렬되어 있는 리스트 a에 정렬 상태를 유지하도록 x를 삽입한다.

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

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

이미 정렬되어 있는 리스트 a에 정렬 상태를 유지하도록 x를 삽입하되, 이미 x가 존재할 경우에 기존 항목 뒤에 삽입한다.

nums = [0, 1, 2, 3, 4, 5]
bisect.insort_right(nums, 3)
print(nums) # [0, 1, 2, 3, 3, 4, 5]

 

bisect 응용하기

7명의 학생 각각의 성적이 33, 99, 77, 70, 89, 90, 100이며 90점 이상은 A, 80점 이상은 B, 70점 이상은 C, 60점 이상은 D, 그 이하는 F일 때 학생들의 성적이 담긴 리스트를 bisect를 이용해 얻어낼 수 있다.

result = []
for score in [33, 99, 77, 70, 89, 90, 100]:
    i = bisect.bisect([60, 70, 80, 90], score) # 점수를 삽입할 위치
    grades = 'FDCBA'
    print(grades[i], end = ' ') # F A C C B A A

bisect(리스트, 점수)로 점수가 리스트의 어느 위치에 들어가야 하는지 인덱스를 받아 grades의 해당 인덱스를 출력하면 그게 바로 학점이 되는 것이다. 예를 들어 95점이라면 90점의 오른쪽에 삽입되어야 하므로 인덱스 4를 반환하고, grades[4] = 'A'이므로 A를 출력하게 되는 것이다. bisect()함수는 기본적으로 오른쪽으로 삽입되는 인덱스를 반환하므로 90점처럼 학점을 구분하는 점수에 걸리게 된다면 오른쪽 인덱스인 4를 반환하여 무리 없이 구현할 수 있다. 이렇게 하면 if ~ else ~문을 사용하여 구구절절 문제를 풀지 않아도 된다.

 

만약 성적 기준이 이상이 아니고 초과라면 어떻게 해야할까? bisect_left를 사용하면 될 것이다.

 

참고

https://docs.python.org/3.6/library/bisect.html#bisect.bisect