파이썬으로 이진 탐색 구현하기
이진 탐색(binary search)은 정렬된 데이터에서 특정한 값을 아주 빠르게 찾는 방법이다. N개의 데이터 중에서 특정한 값 x를 찾을 때, 최악의 경우 N번의 비교가 필요한데, 이진 탐색의 경우 최대 
Home »
이진탐색
bisect – 이진탐색 알고리듬
이진탐색은 데이터가 정렬된 상태일 때, 특정한 값을 매우 우수한 성능으로 탐색할 수 있는 알고리듬으로 실제로도 널리 이용된다. 이진탐색은 정렬된 데이터에서 특정한 값을 찾을 때 사람이 하는 것과 유사하게 처리되는데, 리스트의 한 가운데 지점의 값을 비교하여 찾는 값이 그보다 작으면 왼쪽에 그보다 크면 오른쪽에 있다는 것으로 탐색 범위를 매 시행마다 절반으로 줄여나가기 때문에 특히 규모가 큰 데이터에서 빠르게 조회가 가능하다는 장점이 있다.1 이전에 이진 탐색 알고리듬 적용을 위한 이진 탐색 트리 클래스를 작성하는 내용으로 포스팅을 발행한 적이 있는데, 파이썬은 bisect라는 내장… 더 보기 »bisect – 이진탐색 알고리듬
이진탐색트리 (Binary Search Tree) 구현하기 – python
Binary Search Tree
이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한 구조이다.
이진 탐색 트리는 특정 노드가 어디에 위치하는데에는 크게 관심이 없다. 단지 이를 사용하여 효율적인 탐색을 할 수 있게 한다. 보면 알겠지만 해시테이블이 메모리 공간을 더 사용하고 반대급부로 성능을 얻는 것과는 달리, 이진 탐색 트리는 트리 구조 자체의 특성을 사용하므로 부가적인 메모리 공간의 낭비는 적다고 볼 수 있다.
더 보기 »이진탐색트리 (Binary Search Tree) 구현하기 – python