CHAPTER 4. 효율적인 탐색 & 우선순위 (우선순위 큐, 이진 탐색)

데이터의 양이 많을 때(N >= 100,000) 선형 탐색(O(N))으로는 시간 초과를 피할 수 없다.

 

이때 탐색 시간을 O(log N)으로 대폭 줄여주는 우선순위 큐(Heap)와 이진 탐색(Binary Search)을 핵심 메커니즘 및 필수 템플릿으로 볼 수 있다.

 

4-1. 우선순위 큐 (Heapq)

들어온 순서와 상관없이 항상 최솟값(또는 최댓값)을 최상단(O(1))에 유지하며, 새로운 원소 추가 및 제거 시 O(log N) 만에 트리를 재정렬하는 자료구조임.

 

1. 최소 힙(Min-Heap) 기본 사용법 

파이썬의 heapq 모듈은 기본적으로 가장 작은 수가 맨 위에 오는 최소 힙으로 동작.

import heapq

# 1. 빈 리스트 생성 및 heappush로 원소 추가
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

# 2. 가장 작은 원소 꺼내기 (heappop)
min_val = heapq.heappop(heap)
print(f"가장 작은 값: {min_val}")  # 1 출력
print(f"남은 힙 상태: {heap}")     # [3, 4, 7] (상단에 3이 위치하도록 자동 정렬됨)

 

2. 최대 힙(Max-Heap) 테크닉: (-n, n) 부호 속임수 

파이썬 heapq에는 최대 힙 옵션이 별도로 없으므로, 음수 부호(-)를 붙여 정렬 기준을 뒤집는 튜플 테크닉을 사용합니다.

import heapq

nums = [4, 1, 7, 3]
max_heap = []

# (우선순위, 실제값) 튜플 형태로 넣어줍니다.
for num in nums:
    heapq.heappush(max_heap, (-num, num))

# 가장 큰 값 꺼내기
priority, max_val = heapq.heappop(max_heap)
print(f"가장 큰 값: {max_val}")  # 7 출력

 

 

4-2. 이진 탐색 (Binary Search)

정렬된 배열에서 탐색 범위를 매번 절반(1/2)으로 깎아나가며 원하는 값을 찾는 O(log N) 알고리즘임.

 

1. 필수 전제 조건 & 핵심 포인터 3개

 

• 선결 조건: 데이터가 반드시 사전 정렬(Sort)되어 있어야 함.
• 3개 포인터: start (탐색 시작점), end (탐색 끝점), mid (중간 위치 = (start + end) // 2)

 

2. 이진 탐색 기본 반복문 템플릿

def binary_search(arr, target):
    # 1. 탐색 시작점과 끝점 설정 (인덱스)
    start = 0
    end = len(arr) - 1
    
    # 2. start가 end보다 작거나 같을 때까지 범위를 좁혀가며 탐색
    while start <= end:
        mid = (start + end) // 2  # 정중앙 위치 계산
        
        # 찾고자 하는 값을 발견한 경우 (성공)
        if arr[mid] == target:
            return mid  # 인덱스 위치 반환
        
        # 중간값이 찾으려는 값보다 큰 경우 -> 왼쪽 구간 탐색 (end를 당김)
        elif arr[mid] > target:
            end = mid - 1
            
        # 중간값이 찾으려는 값보다 작은 경우 -> 오른쪽 구간 탐색 (start를 밈)
        else:
            start = mid + 1
            
    # 찾는 값이 리스트에 없는 경우 (실패)
    return -1

# --- 실행 예시 ---
# 반드시 정렬된 상태에서 진행!
sorted_arr = [1, 3, 5, 7, 9, 11, 13, 15]

result_idx = binary_search(sorted_arr, 7)
print(f"7의 위치 인덱스: {result_idx}")  # 3 출력