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

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

[목차]

자주 쓰는 자료구조 비교

구조	강점	대표 활용
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일

프로그래밍