자료구조 선택의 첫걸음

수만 건의 로그에서 멈춰 선 프로그램

웹 서비스에 접속한 사용자 로그 10만 건에서 중복된 IP 주소를 걸러내고 고유 방문자 수를 집계하는 상황을 떠올려 봅니다. 개발자는 자연스럽게 빈 목록을 하나 만들고, 로그를 순회하면서 아직 목록에 없는 IP만 덧붙이는 코드를 작성하기 쉽습니다.

unique_ips = []
for ip in raw_logs:
    if ip not in unique_ips:
        unique_ips.append(ip)

이 코드는 개발 장비에서 수백 건의 샘플 데이터를 시험할 때는 눈 깜짝할 사이에 끝납니다. 하지만 운영 환경에서 하루치 로그 10만 건을 입력으로 넣는 순간, 프로그램은 마치 멈춘 것처럼 수 분 동안 CPU를 100% 점유하며 꼼짝하지 않습니다. 버그나 메모리 누수가 발생한 것이 아닙니다. 선택한 저장 구조가 수행하려는 연산에 전혀 맞지 않았기 때문입니다.

목록에 원소를 보관하는 순차 구조는 특정 값이 내부에 존재하는지 검사할 때 첫 번째 항목부터 끝까지 일일이 대조합니다. 고유 IP가 쌓여 갈수록 한 번 검사할 때 비교해야 하는 횟수가 늘어나며, 결과적으로 10만 건을 처리하기 위해 수십억 번의 비교 작업이 누적됩니다. 반면 이 저장소를 해시 기반 구조로 단 한 줄만 바꾸면 동일한 작업이 1초도 걸리지 않고 완료됩니다. 프로그래밍에서 자료구조(Data Structure)의 선택이 알고리즘의 복잡한 기교보다 앞서 프로그램의 성패를 가르는 첫걸음인 이유가 여기에 있습니다.

순서와 해시가 만드는 탐색 비용의 격차

데이터를 다룰 때 가장 먼저 마주하는 고민은 값을 어떤 형태로 메모리에 보관할 것인가입니다. 복잡한 알고리즘을 구현하지 않더라도 언어가 기본 제공하는 선형 구조와 해시 기반 구조의 동작 원리를 이해하는 것만으로 대다수의 병목 현상을 사전에 방지할 수 있습니다.

선형 구조의 대표 주자인 리스트(List)는 원소가 들어온 순서를 충실히 유지합니다. 배열 기반으로 동작하므로 몇 번째 원소인지 인덱스를 알고 있다면 O(1)의 상수 시간에 즉시 접근할 수 있습니다. 그러나 특정 값이 리스트 안에 포함되어 있는지를 확인하는 in 연산은 데이터 크기 N에 정비례하는 O(N)의 선형 탐색 시간을 요구합니다.

반면 집합(Set)은 데이터의 순서를 보장하지 않고 중복을 원천 차단하는 대신, 내부적으로 해시 테이블을 활용합니다. 값을 해시 함수에 통과시켜 계산된 고유 버킷 주소로 직접 찾아가기 때문에, 내부에 데이터가 수십만 건 들어차 있어도 평균 O(1)의 일정한 시간에 원소의 존재 여부를 즉시 판정합니다.

고유 식별자와 연관된 상세 정보를 짝지어 관리해야 한다면 딕셔너리(Dictionary)가 최적의 선택지입니다. 집합과 마찬가지로 해시 테이블을 기반으로 키를 관리하므로, 특정 키에 대응하는 값을 조회하거나 수정하는 비용이 데이터 총량과 무관하게 평균 O(1)로 유지됩니다.

네 가지 기본 구조의 특성과 비교

애플리케이션을 설계할 때는 다루려는 데이터가 순서를 보존해야 하는지, 중복을 허용하는지, 단일 값인지 키-값 매핑인지에 따라 적절한 구조를 선별합니다.

그림: 기본 자료구조 4종의 연산 특성과 탐색 비용 비교

이 네 가지 구조는 서로 다른 연산 비용과 장단점을 갖추고 있으므로, 빈번하게 발생하는 연산이 무엇인지에 따라 선택 기준을 세워야 합니다.

Python 코드로 관찰하는 연산의 차이

다음 예제는 기술 태그 목록을 바탕으로 리스트, 집합, 딕셔너리가 데이터를 다루는 방식과 탐색 특성의 차이를 검증합니다. 외부 라이브러리 설치 없이 Python 기본 기능만으로 실행할 수 있습니다.

raw_tags = ["Python", "Docker", "Python", "FastAPI", "Docker"]
unique_tags = set(raw_tags)
study_hours = {"Python": 20, "Docker": 15, "FastAPI": 10}
 
print(f"전체 태그 수(리스트): {len(raw_tags)}")
print(f"고유 태그 수(집합): {len(unique_tags)}")
print(f"'Docker' 존재 확인(집합): {'Docker' in unique_tags}")
print(f"'FastAPI' 학습 시간(딕셔너리): {study_hours['FastAPI']}시간")

터미널에서 위 코드를 실행하면 다음과 같은 예시 출력을 확인할 수 있습니다.

전체 태그 수(리스트): 5
고유 태그 수(집합): 3
'Docker' 존재 확인(집합): True
'FastAPI' 학습 시간(딕셔너리): 10시간

출력 결과에서 나타나듯 리스트는 입력된 5개 원소와 그 순서를 온전히 유지합니다. 반면 집합은 중복된 "Python"과 "Docker"를 즉시 병합하여 고유 원소 3개만을 남깁니다. 집합에 in 연산자를 적용하면 수십만 개의 데이터가 있어도 한 번의 해시 조회로 존재를 확인합니다. 딕셔너리는 "FastAPI"라는 문자열 키를 전달받아 그에 대응하는 값 10을 즉시 꺼내옵니다.

대기열 처리를 위한 양단 큐의 활용

리스트는 마지막 위치에 원소를 추가(append)하거나 꺼내는(pop) 작업이 O(1)로 매우 빠릅니다. 하지만 맨 앞의 원소를 꺼내는 pop(0) 연산이나 특정 위치에 원소를 끼워 넣는 insert 연산은 뒤따르는 모든 원소의 메모리 주소를 한 칸씩 앞으로 당겨야 하므로 O(N)의 비용이 듭니다.

작업 대기열이나 이벤트 메시지 큐처럼 먼저 들어온 요청을 먼저 처리해야 하는 FIFO(First-In, First-Out) 구조가 필요하다면, 표준 라이브러리의 양방향 큐(Deque, collections.deque)를 도입해야 합니다. 덱은 내부적으로 양방향 연결 리스트 형태의 블록 메모리를 관리하므로 양쪽 끝에서의 추가와 제거를 모두 O(1)에 처리합니다.

이러한 자료구조 선택과 인덱싱 원리는 대규모 언어 모델 파이프라인의 검색 최적화로도 이어집니다. 예를 들어 RAG 색인과 검색·생성 분리하기에서 다루는 벡터 데이터베이스는 수만 개의 문서 임베딩 중에서 사용자의 질문과 가장 가까운 문맥을 찾아내기 위해 단순 목록 순회 대신 계층형 탐색 그래프나 트리 기반의 공간 색인 구조를 사용합니다. 데이터가 많아질수록 기본 연산의 시간 비용을 줄이는 자료구조의 선택이 전체 애플리케이션의 성능을 결정짓습니다.

[참고] 해시 충돌과 최악의 시간 복잡도

집합과 딕셔너리의 평균 시간 복잡도는 O(1)이지만, 서로 다른 키가 동일한 해시 버킷에 배정되는 해시 충돌이 극단적으로 누적되면 최악의 경우 O(N)으로 성능이 저하될 수 있습니다. Python은 정교한 오픈 어드레싱 알고리즘과 무작위 시드 기반 해시 설계를 적용해 일반적인 환경에서 안정적인 상수 시간 조회를 보장합니다.

참고 문서

• Python Documentation — Data Structures
• Python Documentation — collections.deque
• Python Time Complexity Reference