파이썬으로 이진 탐색 구현하기

이진 탐색(binary search)은 정렬된 데이터에서 특정한 값을 아주 빠르게 찾는 방법이다. N개의 데이터 중에서 특정한 값 x를 찾을 때, 최악의 경우 N번의 비교가 필요한데, 이진 탐색의 경우 최대 log_{2}N만큼의 비교를 하게 된다. 즉 자료의 크기가 클수록 선형 탐색에 비해 성능이 매우 우수해진다. 다만 이진 탐색은 자료가 정렬되어 있다는 전제가 필요하다. (이 때문에 컴퓨터 과학에서는 정렬이 매우 중요하고, 성능이 좋은 정렬 알고리듬을 만들기 위해 많은 노력이 있어왔다.)

파이썬으로 이진 탐색 구현하기 더보기

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() 함수는 xa에 존재하는지 여부는 관심이 없기 때문에 a의 모든 원소보다 x가 크다면 ilen(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_leftinsort_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. 그래서 컴퓨터 과학에서는 정렬 알고리듬이 매우 중요하게 다뤄진다. 

이진탐색트리 (Binary Search Tree) 구현하기 – python

Binary Search Tree

이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한 구조이다.

이진 탐색 트리는 특정 노드가 어디에 위치하는데에는 크게 관심이 없다. 단지 이를 사용하여 효율적인 탐색을 할 수 있게 한다. 보면 알겠지만 해시테이블이 메모리 공간을 더 사용하고 반대급부로 성능을 얻는 것과는 달리, 이진 탐색 트리는 트리 구조 자체의 특성을 사용하므로 부가적인 메모리 공간의 낭비는 적다고 볼 수 있다.
이진탐색트리 (Binary Search Tree) 구현하기 – python 더보기