해시 맵은 어떻게 알고리즘을 최적화하나요?

Question

Accepted Answer

**해시 맵**(딕셔너리)은 **평균 O(1)** 조회, 삽입, 삭제를 제공합니다. O(n) 메모리를 속도와 맞바꿈으로써, 반복 스캔을 즉각적인 조회로 대체하여 많은 O(n²) 알고리즘을 O(n)으로 바꿉니다.

## 개념

매번 리스트를 검색하는 대신, 본 적 있는 값을 해시 맵에 저장하고 상수 시간에 멤버십을 확인합니다.

## 예시: O(n) two-sum

```python
def two_sum(nums, target):
    seen = {}                          # 값 -> 인덱스
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) 조회
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

맵이 없으면 이것은 O(n²)이지만, 맵을 사용하면 한 번의 순회입니다.

## 흔한 용도

- 셋을 이용한 **중복 제거 / 멤버십**.
- **빈도 카운팅**(`Counter`).
- 키 기준 **그룹화 / 인덱싱**.
- 결과의 **캐싱 / memoization**.

## 복잡도

- **평균:** 연산당 O(1). **최악:** 심한 충돌 시 O(n). **공간:** O(n).

## 함정

키는 **해시 가능**하고 불변이어야 합니다. 최악의 충돌은 성능을 저하시킵니다. 해시 맵은 순서가 없습니다(순서가 중요하면 순서 있는 변형을 사용하세요).

## 왜 중요한가

해싱은 코딩 면접과 실제 시스템에서 가장 흔한 단일 최적화입니다 — "몇 번이고 다시 검색"을 "한 번 조회"로 바꿉니다.

공간과 시간을 맞바꾸는 트레이드오프는 반복되는 엔지니어링 지렛대입니다.

빈도 카운팅, 캐싱, 인덱싱 모두 이 하나의 아이디어에 기반합니다.