문제에 맞는 데이터 구조를 어떻게 선택하나요?

Question

Accepted Answer

접근 패턴에서 **가장 빈번한 연산이 가장 저렴한** 구조를 고르세요. 수행할 연산을 나열하고, 그 빈도를 추정한 뒤, 구조의 강점에 맞춰보는 것부터 시작합니다.

## 의사결정 체크리스트

```text
1. 데이터에 어떻게 접근하는가?  index로 -> array
                              key로   -> hash map
                              순서로  -> tree / heap
2. 순서가 필요한가?            정렬    -> balanced BST / 정렬된 array
                              FIFO    -> queue
                              LIFO    -> stack
3. 중간에 자주 삽입하는가?     -> linked list
4. 빠른 "본 적 있나?"가 필요?   -> set / hash map
5. "다음으로 최선/최소/최대"?  -> heap (priority queue)
```

## 연산을 복잡도에 맞추기

| 필요 | 최선의 구조 | 핵심 연산 비용 |
|---|---|---|
| index로 임의 접근 | dynamic array | O(1) |
| key로 조회 | hash map | O(1) 평균 |
| 정렬 + 범위 질의 | balanced BST | O(log n) |
| 반복적인 min/max | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| 접두사 검색 | trie | O(L) |

## 예시 추론

```text
"거대한 파일에서 가장 빈번한 단어 10개를 찾아라."
 - 빈도 세기        -> hash map (O(1) 갱신)
 - 상위 10개 유지   -> 크기 10의 min-heap (단어당 O(log 10))
```

## 왜 중요한가

잘 선택하는 것은 종종 O(n)과 O(n²) 해법의 차이입니다. 성능에 미치는 가장 큰 단일 지렛대입니다.

면접관은 바로 이 추론을 시험합니다. 구조를 암기하는 게 아니라 요구사항을 연산 비용에 매핑하는 모습을 보고 싶어 합니다.

index로 임의 접근	dynamic array	O(1)
key로 조회	hash map	O(1) 평균
정렬 + 범위 질의	balanced BST	O(log n)
반복적인 min/max	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
접두사 검색	trie	O(L)