알고리즘과 자료구조 선택 가이드: 시간복잡도와 활용 예

알고리즘 문제를 풀 때 자료구조 이름을 많이 아는 것보다 어떤 연산이 얼마나 자주 필요한지를 먼저 적는 것이 중요합니다. 입력 크기와 필요한 연산을 확인한 뒤 가장 단순한 구조부터 선택하세요.

자주 쓰는 자료구조 비교

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가 입력보다 매우 작고 결과 일부만 필요하면 힙 기반 접근을 고려할 수 있습니다.

선택 순서

1. 입력 최대 크기와 메모리 제한을 적습니다.
2. 조회, 삽입, 삭제, 최솟값, 순서 유지 중 핵심 연산을 찾습니다.
3. 완전 탐색으로 정답 조건을 명확히 합니다.
4. 병목 연산만 더 나은 자료구조나 알고리즘으로 바꿉니다.
5. 작은 입력과 경계값으로 검증한 뒤 측정합니다.

공식 참고자료

• Python deque 문서
• Python heapq 문서
• Python bisect 문서

관련 글

• 초보자를 위한 실전 코딩 문제풀이 학습법
• 파이썬으로 시작하는 쉽고 재미있는 코딩

내용 검토 및 업데이트: 2026년 8월 27일