[알고리즘 리뷰] 이분 탐색 & 이분 탐색 트리

Series: 알고리즘 리뷰

나동빈님의 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 바탕으로 정리한 내용이 포함되어 있습니다.

0. 알고리즘에서 이분 한다의 핵심

“절반씩 줄인다” ← ChatGPT도 너 정말 핵심을 찔렀어할 핵심 개념

여기서 더 나아가면 3갈래 길이 나오는데 :

알고리즘	무엇을 절반으로?	언제 씀?
이분 탐색	정렬된 배열의 범위	고정된 데이터에서 값 찾기
파라메트릭 서치	답의 후보 범위	최대로/최소로 문제
이분 탐색 트리	트리의 서브트리	데이터가 계속 추가되거나 삭제 될 때

위 셋다 시간복잡도 O(logN)을 뽑고, 결과적으로 뿌리는 “절반씩 줄인다” 핵심임

1. 이분 탐색

정렬된 데이터에서 매번 탐색 범위를 절반씩 줄이며 값을 찾는 방법

술자리 첫 만남에서 나이 맞추기할 때 업다운으로 맞추는거랑 똑같음

순차 탐색과 비교한 이분 탐색의 장점은 매우 효율적인 탐색(후보군을 절반씩 줄여서 보기 때문).

방법	복잡도	100만개 데이터 기준
순차 탐색	O(N)	최대 100만번
이분 탐색	O(log N)	약 20번

매우 많은 데이터 쌍에서도 50번도 안되는 탐색 횟수로 값을 찾아갈 수 있음

단, 데이터가 정렬돼있어야한다는 전제가 필요

정렬이 안돼있다면 탐색 시 절반을 버릴 수 없음

이분 탐색의 뼈대

low - 찾는 범위의 맨 앞
high - 찾는 범위의 맨 끝
mid - low와 high 사이의 중간 값

⇒ low ~ high 사이에 있는 mid를 뽑아 조건을 만족하는지 판별 후, low 혹은 high을 업데이트해서 절반 씩 탐색하도록…

코드

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:              # 1. 등호로 루프 조건 걸기
        mid = (low + high) // 2     # 2. 덧셈으로 mid 뽑기

        if arr[mid] == target:      # 찾으면 리턴
            return mid
        elif arr[mid] > target:     # 찾는 값이 더 작다 -> 왼쪽 절반 범위 보기
            high = mid - 1          # 3. -1 줘서 mid의 왼쪽 부분만 루프 돌도록
        else:                       # 찾는 값이 더 크다 -> 오른쪽 절반 범위 보기
            lo = mid + 1            # 3. +1 줘서 mid의 오른쪽 부분만 루프 돌도록

    return None                     # 못 찾음

주석 번호 순으로 체크하여 구현하면 쉬움

이 파이썬은 다 해줍니다

파이썬 표준 라이브러리에 이미 이분 탐색이 구현돼있다. C로 구현되어 있기에 직접 구현 보다 약 3배 빠름

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 4, 6, 8]

bisect_left(a, 4)     # 2  <- 4가 시작되는 위치
bisect_right(a, 4)    # 5  <- 4가 끝나는 다음 위치

예시

# 1. 특정 값의 개수
bisect_right(a, 4) - bisect_left(a, 4)      # 3

# 2. 범위 [3, 6] 안의 개수
bisect_right(a, 6) - bisect_left(a, 3)      # 4

# 3. 존재 여부
def exists(a, x):
    i = bisect_left(a, x)
    return i < len(a) and a[i] == x

답을 이분 탐색 해보기 (파라메트릭 서치)

위까지는 배열에서 값 찾기 였지만, 실전 문제에서는 보통:

~를 최소로 하는 어떤 값을 찾으시오 / 최소 M을 만족하는 ~의 최댓값은? / … 등등

이런 식으로 어떤 조건을 만족하는 답을 찾으라고 나옴.

그래서 발상을 뒤집어볼 것

답이 얼마인가? ⇒ “조건을 만족하는 D가 답이 될 수 있는가? (예/아니오)”

뼈대

low, high = 최솟값, 최댓값
result = 0

while low <= high:
    mid = (low + high) // 2
    if 가능한가(mid):          # 조건을 따져보고
        result = mid         # 가능할 때 mid를 답 후보군으로 저장
        low = mid + 1        # 더 큰 값 도전
    else:                    # 불가능하면
        high = mid - 1       # 그냥 이분탐색

print(result)

2. 이분 탐색 트리 (BST)

이분 탐색의 한계

정렬된 배열은 삽입 혹은 삭제에 O(N)이 걸림. 중간에 값을 하나 끼워넣으려면 뒤 원소를 전부 밀어야 함

리스트가 커질수록 삽입이 더 오래걸리게 됨. 정확히는

위치 찾기 cost : O(log N)
원소 밀어서 넣기 cost : O(N)

⇒ 흠 그럼 정렬을 유지하면서 삽입과 삭제도 O(log N)일 순 없을까? → 트리를 써보자

이분 탐색 트리 구조

                8
              /   \
            3      10
           / \       \
          1   6       14
             / \      /
            4   7   13

어떤 노드를 기준으로, 왼쪽의 서브트리는 전부 작고 오른쪽 서브트리는 전부 큼

대가리 8을 기준으로 보면 왼쪽(3, 1, 6, 4, 7)은 전부 작고 오른쪽(10, 14, 13)은 전부 큰 것을 확인 가능.

→ 위 규칙이 모든 노드(예를 들어 3을 뽑고 생각해도)에서 성립.

이 구조의 이점은?

탐색이 이분 탐색과 똑같이 동작함.

찾는 값이 현재 노드보다 작으면 왼쪽 서브트리로 가고 / 오른쪽 서브트리를 한번에 버림 ⇒ 이분 탐색 logic과 동일

코드 구현(예시)

class Node:                                    # 트리 클래스
    def __init__(self, key):
        self.key = key
        self.left = None                       # 왼쪽 서브트리 - 여기에 Node class들이 채워짐
        self.right = None                      # 오른쪽 서브트리 - 여기에 Node class들이 채워짐

def insert(root, key):                         # 삽입 코드
    if root is None:
        return Node(key)                       # 빈 곳에 노드 삽입
    if key < root.key:                         # 이분 탐색 처럼 체크 - 노드랑 키 비교
        root.left = insert(root.left, key)     # 노드보다 작은 값이면 왼쪽 서브 트리만 고름
    elif key > root.key:
        root.right = insert(root.right, key)   # 노드보다 큰 값이면 오른쪽 서브 트리만 고름
    return root                                # 중복은 무시

def search(root, key):                         # 탐색 코드
    while root:
        if key == root.key:
            return True
        root = root.left if key < root.key else root.right
    return False

단점 : 편향

BST의 O(log N)은 트리가 균형 잡혀있는 형태여야만 성립.

1,000개의 데이터를 넣는다고 할 때 해당 데이터가 1, 2, 3, … 오름차순으로 들어가면 트리 높이가 1,000이 됨.

⇒ 정렬된 데이터를 순서대로 넣으면 모든 노드가 오른쪽 자식만 갖기 때문(사실상 연결 리스트랑 다를 것이 없음)

→ 이 경우 O(N)으로 퇴화.

실측 (C 로 시작해서 laude로 끝나는 이름의 교수님 도움)

트리	높이	시간
편향 (오름차순 삽입)	5,000	0.0370초
균형 (무작위로 삽입)	27	0.0003초

약 136배 차이남

이걸 해결한 것은 균형 이진 탐색 트리(Self-balancing BST)

→ 삽입 / 삭제 때마다 트리를 회전시켜 높이를 log N으로 유지한다는데…(중략)

개인적으로 세부적인 구현 방법은 알지 않아도 될 것 같고(코테는 BST이던 Self-balancing BST던 거의 안쓴다고 함), CS 면접 대비 이 알고리즘이 왜 등장했는지 정도만 알면 될 듯

코테에서 BST?

코테에서는 거의 쓸 일이 없을 듯

N = 20,000회 / 조회 20,000회 기준 측정 시간

방법	구축	조회
직접 구현한 BST	0.027초	0.018초
정렬 + `bisect`	0.003초	0.008초
`set`	0.009초	0.001초 ← 압도적

왜 직접 구현한 BST가 가장 느리냐 : 파이썬 객체 생성 cost가 크고, set이나 bisect는 C로 구현돼있어서…

실전에서 BST 대체 무기로는…

필요한 것	파이썬에서는
존재 확인, 중복 제거	`set`
키-값 매칭	`dict` (해시 테이블)
정렬 상태 + 순위/범위 찾기	`sorted` 리스트 + `bisect`
최솟값/최댓값 반복해서 꺼내기	`heapq`

대신 set, dict는 순서가 없기 때문에 항상 정렬 상태를 유지하는 BST를 써야하는 경우도 있긴 할 듯

DB 인덱스의 원리가 BST(BST를 디스크에 맞게 확장한 것이 B-트리)임. CS 면접에서도 나올수도?