자료구조 핵심 정리: 이분 탐색부터 해시 테이블까지

오늘 자료구조의 근본이 되는 개념들을 다시 한번 정리해봤다. 각 자료구조가 어떤 원리로 동작하고, 어떤 상황에서 강점을 보이는지, 그리고 어떤 트레이드오프를 가지고 있는지 깊게 파고들었다.

이분 탐색 (Binary Search)

정렬된 리스트 내에서 특정 값을 찾을 때 엄청나게 유리한 탐색 방식. 리스트의 중간값을 계속 확인하며 탐색 범위를 절반씩 줄여나가는 게 핵심이다.

mid = (first + last) // 2
**O(log N)**이라는 경이로운 시간 복잡도를 가진다.

언제 쓸까?

변수의 범위가 문제 조건에서 굉장히 넓게 제시될 때 (선형 탐색으로는 어림도 없을 때)
완전 탐색이나 DFS로 풀 수 있지만, 시간 초과가 예상될 때
데이터를 정렬하는 것이 가능하거나 이미 되어있을 때

주요 유형

정렬된 배열에서 특정 수 찾기 (가장 기본)
정렬된 배열에서 특정 수가 여러 개 있을 때, 가장 왼쪽 또는 오른쪽 인덱스 찾기
TTTTFFFF 같은 배열에서 첫 번째 T나 마지막 F의 위치 찾기 (경계 찾기)

# 이분 탐색의 정석 코드
def search(target):
    """
    정렬된 nums 배열에 target이 있으면 True, 없으면 False를 반환
    """
    l, r = 0, len(nums) - 1

    # l이 r을 역전하기 전까지, 즉 탐색 범위가 남아있는 동안 반복
    while l <= r:
        mid = (l + r) // 2
        
        if nums[mid] == target:  # mid에서 타겟을 찾음
            return True
            
        elif nums[mid] < target: # mid 값이 타겟보다 작으면
            # 타겟은 무조건 mid보다 오른쪽에 있어야 함
            l = mid + 1
            # why? nums[mid]랑 그 왼쪽은 볼 필요가 없으니까.
            
        else: # nums[mid] > target 인 경우
            # 타겟은 무조건 mid보다 왼쪽에 있어야 함
            r = mid - 1
            # why? 닫힌 조건(l <= r)이라 mid는 확실히 제외하고 간다.
            
    return False

연결 리스트 (Linked List)

여러 개의 노드(Node) 가 기차처럼 줄줄이 연결된 형태. 각 노드는 **데이터(data)**와 다음 노드를 가리키는 **포인터(next)**를 가지고 있다. 리스트의 시작은 헤드(Head) 포인터가 가리킨다.

배열에 비해 데이터 접근 속도는 느리지만, 삽입/삭제가 매우 효율적이다.

Why? 배열과 비교해보자.

데이터 접근
- 배열: 데이터가 메모리에 연속적으로 붙어있어, 인덱스만 알면 주소 계산으로 한 번에 점프 가능 (O(1)).
- 연결 리스트: 데이터가 메모리 곳곳에 비연속적으로 흩어져 있고, next 포인터가 다음 노드를 가리키므로 head부터 순차적으로 탐색해야 함 (O(N)).
데이터 삽입/삭제
- 배열: 중간에 데이터를 삽입/삭제하면, 그 뒤의 모든 데이터를 한 칸씩 밀거나 당겨야 함 (O(N)).
- 연결 리스트: 노드의 포인터(연결 고리)만 바꿔주면 끝. 삭제의 경우, 삭제할 노드(B)와 이전 노드(A)를 찾은 뒤, A의 next를 B의 next로 연결하고 B를 제거하면 끝. 연결 자체는 O(1). (물론, 해당 노드를 찾는 데까지는 O(N)이 걸린다.)

분할 정복 (Divide and Conquer)

큰 문제를 작은 문제로 분할한 뒤, 충분히 작아졌을 때 문제를 해결하며 다시 합치는 알고리즘 설계 전략. 이름 그대로 '나누고 정복한다'.

보통 재귀를 사용하기 때문에, 재귀 호출로 인한 오버헤드나 구현의 복잡성이 단점이 될 수 있다.
대표적인 예: 퀵 정렬, 병합 정렬

## 스택 (Stack) & 큐 (Queue)

스택: LIFO (후입선출)

가장 나중에 들어온 게 가장 먼저 나간다. 프링글스 통을 생각하면 쉽다.

push: 원소 추가
pop: 최상단 원소 제거 및 반환
top 또는 peek: 최상단 원소 확인

큐: FIFO (선입선출)

가장 먼저 들어온 게 가장 먼저 나간다. 은행 창구 줄서기와 같다.

enqueue: 원소 추가 (맨 뒤 rear에)
dequeue: 원소 제거 및 반환 (맨 앞 front에서)

구현 방식 비교

배열 기반:
- 스택: 구현이 간단하지만, 고정된 크기 때문에 오버플로우가 발생할 수 있다. 동적 배열로 확장할 순 있지만, 이 과정에서 O(N)의 성능 저하가 발생한다.
- 큐: 단순 배열로 구현하면 dequeue 시 모든 데이터를 앞으로 당겨야 해서(O(N)) 비효율적이다. 원형 큐로 구현하면 O(1)이 가능하지만, 큐가 꽉 찼는지 비었는지 확인하는 추가 로직이 필요하다.
연결 리스트 기반:
- 크기 제한이 없고 동적 할당이라 공간 효율성이 좋다.
- push, pop, enqueue, dequeue 모두 리스트의 맨 앞/뒤에서 일어나므로 **O(1)**의 시간 복잡도를 가진다.
- 단점: 각 노드가 포인터 저장을 위한 추가 메모리를 사용하고, 데이터가 메모리에 흩어져 있어 참조 지역성이 떨어져 캐시 효율이 낮을 수 있다.

해시 테이블 (Hash Table)

시간-공간 트레이드오프의 대표적인 예시. 메모리 공간을 더 사용하는 대신, 비교할 수 없는 검색 속도를 얻는다.

기본 동작: 키(Key)를 해시 함수에 넣어 해시 값(배열의 인덱스)을 얻고, 이 인덱스를 통해 값(Value)에 **O(1)**으로 직접 접근한다.
좋은 해시 함수의 조건: 결정론적, 효율성, 균등 분포, 눈사태 효과.

문제점: 해시 충돌 (Hash Collision)

서로 다른 키가 같은 해시 값을 가질 때 충돌이 발생한다. 해결 방법은 두 가지.

분리 연결법 (Separate Chaining)
- 동작: 각 버킷(배열의 칸)을 연결 리스트의 입구로 사용. 충돌이 나면 해당 버킷의 연결 리스트에 노드를 추가한다.
- 장점: 구현이 간단하고, 로드 팩터가 1을 넘어도 동작하며 성능 저하가 완만하다.
- 단점: 포인터를 위한 추가 메모리가 필요하며, 최악의 경우(모든 데이터가 한 버킷에 충돌) O(N)이 되어 그냥 연결 리스트가 된다.
개방 주소법 (Open Addressing)
- 동작: 충돌 발생 시, 테이블 내의 다른 빈칸을 찾아 데이터를 저장한다. (선형 탐사, 제곱 탐사, 이중 해싱 등)
- 장점: 추가 자료구조가 필요 없어 메모리 효율이 좋고, 데이터가 연속된 메모리에 있을 확률이 높아 캐시 효율이 좋다.
- 단점:
  - 클러스터링 (군집화): 데이터가 특정 영역에 뭉치는 현상이 발생하기 쉽다.
  - 복잡한 삭제: a,b,c가 충돌하여 5,6,7번 칸에 순서대로 저장됐다고 하자. 여기서 b를 그냥 지워버리면, c를 찾을 때 6번 칸이 비어있다고 판단하여 탐색을 중단, c를 찾지 못하는 문제가 생긴다. 이를 해결하기 위해 '삭제됨(Tombstone)'이라는 상태를 추가하는데, 이 때문에 데이터를 삭제해도 검색 성능이 나아지지 않는다.

로드 팩터 (Load Factor)와 리해싱 (Rehashing)

로드 팩터: 해시 테이블의 건강 상태 지표. 테이블이 얼마나 찼는지를 의미한다.
개방 주소법에서 로드 팩터가 1에 가까워지면 성능이 급격히 저하된다.
로드 팩터가 임계점을 넘으면, 더 큰 테이블을 새로 만들어 모든 데이터를 다시 해싱하는 리해싱을 진행한다. 리해싱 자체는 O(N)의 비용이 들지만, 분할 상환 분석 관점에서 보면 아주 가끔 발생하므로, 평균 시간 복잡도는 여전히 **O(1)**에 가깝다고 본다.