콘텐츠로 건너뛰기
Home » bisect – 이진탐색 알고리듬

bisect – 이진탐색 알고리듬

이진탐색은 데이터가 정렬된 상태일 때, 특정한 값을 매우 우수한 성능으로 탐색할 수 있는 알고리듬으로 실제로도 널리 이용된다. 이진탐색은 정렬된 데이터에서 특정한 값을 찾을 때 사람이 하는 것과 유사하게 처리되는데, 리스트의 한 가운데 지점의 값을 비교하여 찾는 값이 그보다 작으면 왼쪽에 그보다 크면 오른쪽에 있다는 것으로 탐색 범위를 매 시행마다 절반으로 줄여나가기 때문에 특히 규모가 큰 데이터에서 빠르게 조회가 가능하다는 장점이 있다.1

이전에 이진 탐색 알고리듬 적용을 위한 이진 탐색 트리 클래스를 작성하는 내용으로 포스팅을 발행한 적이 있는데, 파이썬은 bisect라는 내장 라이브러리를 제공한다. 이 라이브러리는 별도의 타입이나 클래스를 요구하지 않으면서 몇 가지 함수를 이용해서 기본 리스트에 대해서 이진 탐색을 수행하는 api들을 제공한다.

bisect : Python Starndard Library 참고

이 모듈은 이미 존재하는 리스트가 있을 때[^2] 주어진 값 x 가 이 리스트상에서 위치해야 할 인덱스 값을 구하는 식의 함수들로 구성되며 크게 두 가지로 나뉜다.

  1. 주어진 리스트 a와 값 x 가 있을 때, x 가 위치해야 할 인덱스를 구하는 함수
  2. 그리고 같은 조건에서 값 x를 올바른 위치에 삽입하는 함수

각각의 함수는 _left, _right 접미사가 붙는데, 이는 주어진 값 x와 같은 값이 리스트 내에 있을 때, x의 위치가 동일한 값으로부터 왼쪽에 있을지 오른쪽에 있을지를 결정하는 기준이 된다. (참고로 접미사가 생략되는 경우 _right라고 간주한다.)

  • bisect_left(arr, x, lo=0, hi=len(arr)) : 리스트 a에서 값 x가 들어갈 인덱스를 구한다. 참고로 lo=, hi=는 리스트의 특정 범위 내에서만 이진 탐색을 수행하려할 때 사용한다. (모든 함수에 공통적으로 추가할 수 있는 인자이다.)
  • bisect_right(arr, x) : bisect()와 같은 함수. bisect_left()와 비슷한 동작을 하나, 같은 값이 있으면 그 값의 오른쪽 위치를 취한다.
  • insort(arr, x) : bisect()로 구해진 위치에 x 값을 삽입한다.
  • insort_left(arr, x) : bisect_left()로 구해진 위치에 x값을 삽입한다.

활용하기

이 모듈을 사용하면 별도의 트리 구조 타입을 만들지 않고도 이진 탐색 알고리듬을 활용할 수 있다.

경우에 따라서는 이런 함수 기반 api 보다 클래스를 만드는 것을 더 선호하는 사람들이 있다. java등의 다른 객체 지향 언어에 대한 경험을 갖고 있을수록 이러한 경향을 보이는 듯 하다. 흥미로운 점은 파이썬은 그 자체로 객체 지향 언어이면서 그 내부에서는 흔히 클래스를 만들어서 문제를 해결하는 것을 그리 권장하지 않는 것 같은 인상을 보인다.

클래스를 쓰기보다는 이렇게 함수 번들로 이루어진 API를 제공한다거나, 제너레이터나 데코레이터를 이용해서 가능하면 클래스 구현을 우회할 수 있는 다양한 방법들을 제시한다.

이진 탐색

이미 정렬된 어떤 리스트에 대해서 임의의 값 x가 존재하는지를 검사하는 함수를 작성해보자.

def binary_search(arr, x):
  i = bisect.bisect_left(arr, x)
  return i < len(arr) and arr[i] == x

bisect_left(a, x)의 결과가 i 라 할 때, a[i]는 x보다 크거나 작은 값일 수 있다. 따라서 a[i]가 x와 같은지를 체크해야 한다.  또한 bisect_left() 함수는 x가 a에 존재하는지 여부는 관심이 없기 때문에 a의 모든 원소보다 x가 크다면 i는 len(a)와 같은 값이 나올 것이다. 이 경우는 x가 존재하지 않는 것으로 본다.

리스트를 정렬하기

빈 리스트로부터 insort() 함수를 이용해서 원소를 계속 추가하면 자연스럽게 정렬된 리스트를 얻을 수 있다.  다음 코드는 난수로 생성된 리스트의 각 원소를 insort()를 이용해서 a에 추가해서 정렬된 리스트 a를 얻는 방법을 보인다.

import bisect, random
a = []
b = [random.randrange(1, 50) for _ range(50)]
for x in b:
  bisect.insort(a, x)

점수에 따라 등급나누기

bisect() 를 활용할 수 있는 의외의 방법이 있는데, 바로 특정 점수 구간을 성적을 매길 때 사용하기 좋다는 것이다.  예를 들어 다음과 같은 점수 구간이 있다고 하자. (오른쪽 경계는 포함하지 않음)

  • 0 ~ 50 : F
  • 50 ~ 60 : D
  • 60 ~ 70 : C
  • 70 ~ 90 : B
  • 90 ~ 100 : A

이 때 특정 점수에 따른 그레이드를 결정하기 위해서 흔히 if .. elif .. elif ...로 이어지는 분기문을 많이 쓰는데, 점수 구간 표에서 주어진 점수가 어느 위치에 들어가느냐를 가지고 그 위치를 등급의 인덱스로 써서 간단히 구현할 수 있다.

def get_grade(score):
  r = (50, 60, 70, 90, 100)
  g = 'FDCBA'
  return g[bisect_right(r, score)]

다음페이지에서는 bisect 모듈의 실제 구현 코드를 살펴보자.

bisect 모듈은 실제로 순수 파이썬으로 작성되었다. bisect_left 와 insort_left 의 구현을 살펴보자. 알고리듬 자체가 단순/명확하기 때문에 초보자가 보기에도 어려움이 없을 것이다.

def bisect_left(a, x, lo=0, hi=None):
  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  ## 크거나 같으면 왼쪽 절반으로 범위 축소.
    ## 이 때, lo == hi 가 되면 찾은 것이고, lo > hi 가 되면 없는 것이다.
  return lo
def insort_left(a, x, lo=0, hi=None):
  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
  a.insert(lo, x)
  1. 그래서 컴퓨터 과학에서는 정렬 알고리듬이 매우 중요하게 다뤄진다. ↩
태그: