알고리즘 문제를 풀 때 자료구조 이름을 많이 아는 것보다 어떤 연산이 얼마나 자주 필요한지를 먼저 적는 것이 중요합니다. 입력 크기와 필요한 연산을 확인한 뒤 가장 단순한 구조부터 선택하세요.
[목차]
자주 쓰는 자료구조 비교
| 구조 | 강점 | 대표 활용 |
|---|---|---|
| list/배열 | 인덱스 접근 | 순서 있는 데이터, 순회 |
| dict/해시맵 | 키 조회의 평균 O(1) | 빈도 집계, ID 조회 |
| set | 포함 여부의 평균 O(1) | 중복 제거, 방문 확인 |
| deque | 양끝 삽입·삭제 O(1) | 큐, BFS, 슬라이딩 윈도우 |
| heap | 최솟값 조회와 갱신 | 우선순위 큐, 상위 K개 |
| 트리 | 계층과 범위 표현 | 파일 구조, 구간 질의 |
| 그래프 | 관계 표현 | 경로, 네트워크, 의존성 |
Big O는 구현과 데이터 분포를 단순화한 모델입니다. 해시 충돌, 메모리 사용량과 캐시 효율도 실제 성능에 영향을 줍니다.
빈도 집계: dict
counts = {}
for word in words:
counts[word] = counts.get(word, 0) + 1
각 항목의 빈도를 반복해서 검색해야 한다면 매번 리스트를 세는 방식보다 해시맵이 적합합니다.
최단 간선 수: deque를 이용한 BFS
from collections import deque
def distances(graph, start):
distance = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for next_node in graph[node]:
if next_node not in distance:
distance[next_node] = distance[node] + 1
queue.append(next_node)
return distance
가중치가 없는 그래프의 최단 간선 수에는 BFS가 적합합니다. 가중치가 있으면 조건에 따라 Dijkstra, Bellman-Ford 등 다른 알고리즘을 검토해야 합니다.
상위 K개: heap
import heapq
top_k = heapq.nlargest(3, scores)
전체 정렬은 일반적으로 O(n log n)입니다. K가 입력보다 매우 작고 결과 일부만 필요하면 힙 기반 접근을 고려할 수 있습니다.
선택 순서
- 입력 최대 크기와 메모리 제한을 적습니다.
- 조회, 삽입, 삭제, 최솟값, 순서 유지 중 핵심 연산을 찾습니다.
- 완전 탐색으로 정답 조건을 명확히 합니다.
- 병목 연산만 더 나은 자료구조나 알고리즘으로 바꿉니다.
- 작은 입력과 경계값으로 검증한 뒤 측정합니다.
공식 참고자료
관련 글
내용 검토 및 업데이트: 2026년 8월 27일