자료 구조는 데이터를 저장하고 찾기·추가·삭제·순회 같은 연산을 지원하는 방식이다. 이 문서는 배열·연결 리스트·스택·큐·해시·트리·힙을 실제 예제로 비교하고, 참조 공유와 동점 처리, LRU 캐시 구현과 검증까지 설명한다.
자료 구조는 저장 방식과 연산을 함께 설계한다
자료 구조는 데이터를 조직해 저장하고 필요한 연산을 지원하는 방식이다. 원소를 어디에 두는가뿐 아니라 찾기·추가·삭제·순회가 어떻게 동작하며 무엇을 보장하는지가 중요하다. 같은 값 목록도 배열, 연결 리스트, 집합과 사전으로 표현하면 가능한 연산과 비용이 달라진다.
예를 들어 최근 방문한 문서를 순서대로 보여주는 기능에는 순서가 필요하고, 방문 여부만 확인하는 기능에는 중복 없는 집합이 자연스럽다. 문서 ID로 제목을 찾는 기능에는 키와 값의 대응이 필요하다. 하나의 컨테이너에 모든 역할을 억지로 넣으면 조회가 느려지거나 상태 동기화가 복잡해질 수 있다.
알고리즘과 자료 구조는 함께 선택한다. 너비 우선 탐색에는 먼저 넣은 항목을 먼저 꺼내는 큐가 필요하고, 가장 작은 후보를 반복해서 고르는 작업에는 우선순위 큐가 유용하다. 문제의 연산을 정한 뒤 이를 효율적으로 지원하는 저장 방식을 고르면 선택 근거가 분명해진다.
이 문서는 Python의 기본 컨테이너와 작은 직접 구현을 이용해 원리를 설명한다. 특정 언어의 이름을 추상 개념과 동일하게 취급하지 않으며, 코드 예제는 별도 안내가 없으면 독립적으로 실행한다. 학습용 구현은 동시성·영속성·장애 복구를 모두 갖춘 운영 제품이 아니다.
추상 자료형과 구현을 구분하기
스택은 마지막에 넣은 항목을 먼저 꺼낸다는 연산 계약이고, 그 계약은 배열이나 연결 노드 등으로 구현할 수 있다. 큐와 사전도 마찬가지다. 추상 자료형은 무엇을 할 수 있는지, 구현은 그 연산을 어떻게 수행하는지 설명한다.
인터페이스를 작게 정하면 구현을 바꾸기 쉽다. 작업 대기열의 사용자가 put과 get만 필요하다면 내부 배열의 모든 메서드를 노출할 이유가 없을 수 있다. 내부 표현에 의존하는 코드가 많아지면 자료 구조를 바꿀 때 사용 지점 전체를 수정해야 한다.
연산의 실패 조건도 계약이다. 빈 스택에서 pop을 호출하면 예외를 던질지 특별한 값을 반환할지, 가득 찬 큐에서 대기할지 거절할지 정해야 한다. None이 유효한 데이터라면 None을 빈 상태 표기로 사용하는 방식은 모호해질 수 있다. 값의 범위와 상태 표현을 함께 설계한다.
복잡도는 계약의 일부가 될 수 있지만 전제를 밝혀야 한다. “조회 O(1)”이 최악 보장인지 기대 비용인지, 키 비교 비용을 포함했는지, 확장 시 비용은 어떤지 구분한다. 사용자가 요구하는 것이 평균 처리량인지 개별 요청의 지연 상한인지에 따라 적합한 구현이 달라진다.
배열: 위치 기반 접근과 연속 저장
배열은 인덱스에 따라 원소의 위치를 계산할 수 있는 구조다. 고정 크기 슬롯의 연속 저장 모델에서는 i번째 원소에 빠르게 접근할 수 있다. 다만 Python list처럼 객체 참조를 저장하는 컨테이너와 숫자 값을 조밀하게 저장하는 배열은 내부 메모리 표현이 다르다.
아래 배열에서 인덱스 1의 값은 20이고 이를 25로 바꾸면 [10,25,30]이 된다. 위치를 아는 접근과 값이 어디 있는지 찾는 검색을 구분한다. 인덱스 접근이 빠르다고 특정 값의 검색도 자동으로 상수 시간이 되는 것은 아니다.
가운데에 새 원소를 끼워 넣으면 뒤쪽 원소들의 위치를 옮겨야 할 수 있다. 삭제도 마찬가지다. 반면 연속적인 순회는 메모리 지역성의 이점을 얻기 쉬운 구조다. 시간 복잡도만 같아도 노드를 따라가는 구조와 실제 성능이 달라질 수 있다.
고정 길이인지 늘어날 수 있는지, 원소가 직접 값인지 참조인지, 허용 자료형이 같은지 확인한다. 이미지 픽셀이나 대량 수치 자료처럼 조밀한 저장이 중요한 상황에서는 일반 객체 목록보다 타입이 정해진 배열을 비교할 수 있다.
예제 코드
values = [10, 20, 30]
print(values[1])
values[1] = 25
print(values)실행 결과
20
[10, 25, 30]동적 배열: 크기와 용량
동적 배열은 사용 중인 원소 수와 확보한 저장 용량을 구분한다. 남은 공간이 있으면 끝에 추가하고, 부족하면 더 큰 공간을 확보해 기존 원소를 옮긴다. 확장 정책을 적절히 선택하면 연속된 추가의 분할 상환 비용을 상수 시간으로 만들 수 있다.
특정 추가 한 번은 많은 복사를 수행할 수 있으므로 분할 상환 O(1)과 개별 연산 최악 O(1)은 다르다. 응답 지연이 엄격한 기능에서는 사전 용량 확보나 다른 구조를 검토할 수 있다. 반대로 작은 목록에 과도한 복잡성을 도입하면 유지보수 비용이 더 커질 수 있다.
크기가 늘어날 때마다 정확히 한 칸만 더 할당하면 누적 복사량이 1+2+…+n으로 증가할 수 있다. 여유 용량을 두는 이유는 메모리를 조금 더 사용해 반복 확장 비용을 줄이기 위해서다. 어떤 배율을 쓰는지는 구현마다 다르므로 Python list가 항상 두 배로 늘어난다고 가정하지 않는다.
삭제 후 언제 용량을 줄일지도 정책이다. 매번 즉시 줄이면 추가와 삭제가 번갈아 일어날 때 재할당이 반복될 수 있다. 너무 오래 유지하면 사용량이 줄어도 메모리 점유가 남는다. 시간과 메모리, 작업 패턴을 함께 고려한다.
참조 공유와 얕은 복사
컨테이너를 복사했다고 내부 객체가 모두 독립적인 것은 아니다. 얕은 복사는 바깥 컨테이너를 새로 만들지만 안쪽 객체 참조는 공유할 수 있다. 아래 copied에 행을 추가해도 original 길이는 1이지만, 공유된 내부 사전의 score를 바꾸면 original에서도 9가 보인다.
이 차이는 화면 상태와 설정, 캐시에서 자주 문제가 된다. 복사본을 수정한다고 생각했는데 원본이 바뀌면 어느 깊이에서 같은 객체를 참조하는지 확인한다. 동등한 값인지 동일한 객체인지도 구분해야 한다.
deepcopy 같은 도구는 중첩 데이터를 복제하는 데 도움이 되지만 파일 핸들·연결·공유 자원까지 의미 있게 복제하는 만능 도구는 아니다. 일부 객체는 의도적으로 공유해야 할 수도 있다. 변경할 부분만 새로 구성하거나 소유권을 명확히 하는 설계가 더 적절한 경우가 있다.
자료 구조의 연산 비용을 분석할 때도 복사가 중요한 역할을 한다. 작은 참조 목록을 복사하는 것과 거대한 객체 그래프를 깊게 복사하는 것은 다른 비용이다. “복사 O(n)”에서 n이 바깥 원소 수인지 전체 포함 데이터 크기인지 명시해야 한다.
예제 코드
original = [{'score': 1}]
copied = original.copy()
copied[0]['score'] = 9
copied.append({'score': 3})
print(original[0]['score'])
print(len(original), len(copied))실행 결과
9
1 2연결 리스트: 노드 사이의 연결
연결 리스트는 각 노드가 값과 다음 노드의 연결을 저장하는 방식이다. 이중 연결 리스트는 이전 노드도 가리킨다. 노드가 메모리에서 연속할 필요가 없으며 특정 연결을 바꾸어 삽입·삭제할 수 있다.
“연결 리스트의 삭제는 O(1)”이라는 설명에는 삭제할 노드와 필요한 이웃 정보를 이미 알고 있다는 조건이 있다. 값이 같은 노드를 먼저 찾아야 하면 탐색 비용이 추가된다. 단일 연결 리스트에서는 이전 노드를 알아야 연결을 우회시키는 작업이 간단해지는 경우가 많다.
인덱스 i로 바로 접근하려면 보통 앞에서 연결을 따라가야 한다. 각 노드의 포인터 저장 비용과 개별 할당, 캐시 지역성도 고려한다. 배열보다 삽입이 유리한 상황이 있어도 모든 작업에서 더 빠르다는 뜻은 아니다.
아래 예제는 사전을 작은 노드로 사용해 A-B-C를 연결하고 순회한다. 실제 범용 연결 리스트 클래스는 빈 상태, 머리와 꼬리 갱신, 삭제 후 연결, 반복자 수명과 노드 소유권을 더 다뤄야 한다. 순환 연결을 잘못 만들면 종료 조건 없는 순회가 끝나지 않을 수 있다.
예제 코드
third = {'value': 'C', 'next': None}
second = {'value': 'B', 'next': third}
head = {'value': 'A', 'next': second}
values = []
node = head
while node is not None:
values.append(node['value'])
node = node['next']
print(values)실행 결과
['A', 'B', 'C']스택: 마지막 작업부터 되돌리기
스택은 후입선출 구조다. 마지막에 넣은 항목을 먼저 꺼내므로 되돌리기 기록, 중첩 구문 처리, 깊이 우선 탐색의 대기 상태 등에 사용한다. push와 pop이라는 이름보다 순서 계약이 핵심이다.
아래 A를 넣고 B를 넣은 뒤 pop하면 B가 나온다. 남은 것은 A다. Python list의 끝 append와 pop은 스택 구현에 사용할 수 있다. 앞쪽에 삽입하고 삭제하는 방식으로 같은 계약을 만들 수도 있지만 동적 배열에서 이동 비용이 커질 수 있다.
빈 스택 처리는 반드시 정한다. 예제는 비어 있는지 확인한 후 empty를 표시한다. 여러 실행 흐름이 같은 스택을 공유한다면 “비어 있지 않은지 확인한 뒤 꺼내기” 두 단계 사이에서 상태가 바뀔 수 있으므로 단일 스레드 예제를 그대로 동시성 코드로 확대하지 않는다.
되돌리기 기능은 스택 하나로 모든 의미가 해결되지는 않는다. 작업을 취소하는 역연산, 다시 실행 기록, 외부 시스템의 부수 효과와 실패를 별도로 정의해야 한다. 자료 구조는 작업 순서를 보관하지만 업무 동작의 복구 가능성을 자동으로 만들지는 않는다.
예제 코드
stack = []
stack.append('A')
stack.append('B')
print(stack.pop())
print(stack)
stack.pop()
print('empty' if not stack else 'not empty')실행 결과
B
['A']
empty실전 스택 예제: 괄호 짝 검사
중첩된 괄호는 가장 최근에 열린 괄호부터 닫혀야 한다. 스택은 아직 닫히지 않은 여는 괄호를 저장한다. 닫는 괄호를 만나면 스택 맨 위와 종류가 맞는지 확인하고, 입력이 끝났을 때 남은 괄호가 없어야 한다.
아래 ([{}])는 True이고 ([)]는 False다. 여는 괄호와 닫는 괄호의 개수만 세면 두 번째 경우를 잘못 허용할 수 있다. 순서와 중첩 관계를 저장해야 하는 이유다. 닫는 괄호가 먼저 나오거나 끝까지 열린 괄호가 남는 경우도 거절한다.
각 문자를 한 번 읽고 각 괄호를 최대 한 번 넣고 빼므로 문자 접근과 스택 연산의 통상적인 모델에서 O(n) 시간, 최악 O(n) 공간이다. 모두 여는 괄호라면 입력 길이만큼 대기 상태가 쌓일 수 있다.
이 함수는 괄호 외 문자를 무시한다. 프로그래밍 언어의 문자열 리터럴이나 주석 안에 있는 괄호를 별도로 해석하지 않으므로 실제 언어 파서가 아니다. 문법 분석에 사용하려면 토큰화와 문자열·이스케이프 규칙을 먼저 처리해야 한다.
예제 코드
def balanced(text):
matching = {')': '(', ']': '[', '}': '{'}
stack = []
for char in text:
if char in '([{':
stack.append(char)
elif char in matching:
if not stack or stack.pop() != matching[char]:
return False
return not stack
for text in ['([{}])', '([)]', ')(', '(((', '']:
print(balanced(text))실행 결과
True
False
False
False
True큐와 덱: 들어온 순서대로 처리하기
큐는 선입선출 구조다. 먼저 들어온 항목을 먼저 꺼내므로 작업 대기열과 너비 우선 탐색에 자연스럽다. 덱은 양쪽 끝에서 추가와 삭제를 지원한다. Python의 deque는 이런 양 끝 연산을 위한 컨테이너다.
아래 A,B,C를 뒤에 넣고 앞에서 꺼내면 A가 나온다. 이어 urgent를 앞에 넣으면 남은 순서는 urgent,B,C가 된다. 큐의 공정한 선입선출 규칙을 유지하려면 운영 코드에서 임의로 앞 삽입을 허용할지 정해야 한다. 덱이 제공하는 모든 기능을 사용자에게 노출하는 것이 반드시 좋은 인터페이스는 아니다.
Python list의 pop(0)은 뒤 원소들을 이동시키는 비용이 생길 수 있다. 항목을 앞에서 반복해서 꺼내는 작업에서는 deque를 비교한다. 반대로 덱의 가운데 임의 위치 접근을 배열과 같은 비용으로 기대하면 안 된다. 주요 연산이 무엇인지에 따라 선택한다.
대기열의 크기가 무제한이면 생산 속도가 소비 속도보다 빠를 때 메모리가 계속 늘 수 있다. 용량 제한, 거절·대기 정책과 작업 실패 처리까지 함께 설계해야 한다. 컨테이너 이름만 큐라고 해서 작업이 영속적으로 보관되거나 장애 후 복구되는 것은 아니다.
예제 코드
from collections import deque
queue = deque(['A', 'B', 'C'])
print(queue.popleft())
queue.appendleft('urgent')
print(list(queue))실행 결과
A
['urgent', 'B', 'C']링 버퍼: 고정 공간을 순환 사용하기
링 버퍼는 고정 크기 배열을 원형처럼 사용해 앞과 뒤 인덱스를 순환시킨다. 끝에 도달하면 나머지 연산으로 처음 위치로 돌아온다. 로그의 최근 일부만 보관하거나 일정한 버퍼 공간을 사용하는 작업에 적합할 수 있다.
head와 tail이 같을 때 빈 상태인지 가득 찬 상태인지 구분해야 한다. 원소 수를 따로 저장하거나 한 칸을 비워 두는 등 구현 규칙이 필요하다. 가득 찼을 때 새 입력을 거절할지 오래된 항목을 덮을지에 따라 데이터 손실 의미가 달라진다.
아래 maxlen=3인 deque에 A,B,C,D를 차례로 넣으면 가장 오래된 A가 빠지고 B,C,D가 남는다. 최근 이력이라는 요구에는 맞지만 반드시 모든 작업을 처리해야 하는 큐에 같은 정책을 쓰면 작업이 조용히 사라질 수 있다. API의 용량 제한 동작을 확인해야 한다.
링 버퍼라는 구조만으로 스레드 안전성이나 lock-free 성질이 생기지는 않는다. 생산자·소비자 수, 메모리 가시성, 원자적 인덱스 갱신을 별도로 설계해야 한다. 단일 실행 흐름의 예제를 공유 메모리 통신 구조로 그대로 옮기지 않는다.
예제 코드
from collections import deque
recent = deque(maxlen=3)
for item in ['A', 'B', 'C', 'D']:
recent.append(item)
print(list(recent))실행 결과
['B', 'C', 'D']집합: 존재 여부와 중복 제거
집합은 중복 없는 원소를 표현하며 포함 여부, 합집합과 교집합 같은 연산에 적합하다. 방문 여부를 기록하거나 두 그룹의 공통 항목을 찾는 경우에 사용할 수 있다. 순서와 중복 개수는 별도의 요구사항이다.
아래 a와 b의 교집합은 2,3이고 a에만 있는 값은 1이다. 집합 순회 순서를 출력 계약으로 삼지 않기 위해 sorted로 표시한다. 정렬 표시 비용은 집합 연산 비용과 별도로 추가된다.
Python 집합의 원소는 해시 가능해야 한다. 변경 가능한 목록을 그대로 원소로 넣으려 하면 TypeError가 발생한다. 목록을 튜플로 바꿀 수 있는지는 데이터 의미에 따라 판단하며, 내부에 해시 불가능한 값이 있으면 단순 변환만으로 해결되지 않을 수 있다.
중복 제거가 항상 정답은 아니다. 주문 목록에서 같은 상품 두 줄을 별개 구매로 봐야 한다면 집합으로 바꾸는 순간 정보가 사라진다. 무엇을 같은 항목으로 볼지, 원래 순서를 유지할지, 개수를 보관할지를 먼저 정한다.
예제 코드
a = {1, 2, 3}
b = {2, 3, 4}
print(sorted(a & b))
print(sorted(a - b))
try:
a.add([5])
except TypeError as error:
print(type(error).__name__)실행 결과
[2, 3]
[1]
TypeError해시 맵: 키로 값을 찾기
맵은 키에 대응하는 값을 저장한다. 해시 맵은 키의 해시를 이용해 후보 위치를 정하고 동등성 비교로 실제 키를 구별한다. 해시값이 같다는 사실만으로 두 키가 같은 것은 아니므로 충돌 처리가 필요하다.
아래 고객별 금액 집계는 키가 없을 때 0부터 시작해 합계를 누적한다. Ada의 결과는 2000이다. 같은 키로 다시 대입하면 이전 값을 덮어쓰는 사전과, 여러 값을 묶는 다중 맵은 다른 구조다. 한 고객의 주문 이력을 모두 보관하려면 값으로 목록 등을 사용해야 한다.
키의 동등성과 해시의 계약이 중요하다. 같은 것으로 비교되는 키는 일관된 해시를 가져야 하며, 저장된 동안 해시에 영향을 주는 상태를 바꾸면 검색이 깨질 수 있다. 일반적으로 불변 식별자를 키로 사용하는 이유다. 사용자 정의 객체의 해시 구현은 이런 규칙을 지켜야 한다.
해시 조회의 기대 비용과 최악 비용, 테이블 확장과 키 계산 비용을 구분한다. 삽입 순서를 보존하는 언어의 사전이라도 키를 정렬한 순서로 보관하는 트리 맵과 같지는 않다. 범위 검색이 필요하면 별도 구조를 고려한다.
예제 코드
totals = {}
for customer, amount in [('Ada', 1200), ('Lin', 500), ('Ada', 800)]:
totals[customer] = totals.get(customer, 0) + amount
print(totals['Ada'])
print(totals.get('Sam', 0))실행 결과
2000
0빈도표와 다중 값: 필요한 정보를 남기기
단순 집합은 존재 여부만 남기므로 중복 횟수를 잃는다. 단어 빈도나 재고 수량처럼 개수가 필요하면 값별 카운터를 사용한다. 키 하나에 여러 항목이 필요하면 목록이나 집합을 값으로 저장하는 모델을 사용할 수 있다.
아래 Counter는 red 두 번과 blue 한 번을 구분한다. 고객별 주문 ID를 defaultdict(list)로 모으면 Ada에게 101과 103이 연결된다. 누적 합과 원본 목록 보관은 다른 요구이며, 합계만 저장하면 나중에 개별 주문을 복원할 수 없다.
defaultdict의 인덱스 접근은 없는 키에 기본 값을 만들 수 있다. 단순 조회라고 생각한 코드가 상태를 추가하는지 확인한다. get을 사용하는 방식과 같은 동작이라고 가정하지 않는다. 자료 구조의 편리한 기본 동작이 숨겨진 변경을 만들 수 있다.
중복의 의미도 자료마다 다르다. 같은 문자열이 여러 번 나온 것과 같은 ID의 이벤트를 중복 수신한 것은 다르다. 전자는 빈도에 포함할 수 있지만 후자는 중복 처리 방지를 위해 식별자를 기록해야 할 수 있다. 컨테이너 선택 전에 업무적 동일성을 정의한다.
예제 코드
from collections import Counter, defaultdict
counts = Counter(['red', 'blue', 'red'])
print(counts['red'], counts['green'])
orders = defaultdict(list)
for customer, order_id in [('Ada', 101), ('Lin', 102), ('Ada', 103)]:
orders[customer].append(order_id)
print(orders['Ada'])실행 결과
2 0
[101, 103]이진 탐색 트리와 균형
이진 탐색 트리는 노드의 키를 기준으로 작은 값과 큰 값의 하위 트리를 구분한다. 이 성질을 이용하면 한쪽 하위 트리를 버리면서 검색하고, 중위 순회로 키 순서를 얻을 수 있다. 중복 키를 어떻게 저장하는지는 구현 계약으로 정한다.
검색 비용은 트리 높이에 비례한다. 균형이 잘 유지되면 높이가 로그 수준이지만, 정렬된 값을 단순한 비균형 트리에 차례로 넣으면 한쪽으로 길게 늘어져 선형 높이가 될 수 있다. “트리는 조회 O(log n)”이라는 말에는 균형 조건이 필요하다.
AVL 트리와 레드-블랙 트리 같은 균형 트리는 삽입·삭제 때 회전과 추가 정보를 관리해 높이와 관련된 불변식을 유지한다. 조회뿐 아니라 변경 비용과 구현 복잡성이 생긴다. 이미 정렬된 고정 배열에 이진 탐색을 쓰는 방식과 비교할 때는 갱신 빈도가 중요한 기준이다.
트리 키의 비교 기준도 일관되어야 한다. 저장 후 정렬에 영향을 주는 키 값을 몰래 바꾸면 검색 경로의 전제가 깨진다. 값 변경이 필요하면 적절히 제거하고 다시 삽입하거나 키와 변경 가능한 부가 자료를 분리한다. 해시 맵과 마찬가지로 내부 불변식을 유지하는 책임이 중요하다.
정렬된 배열과 범위 조회
값이 정렬되어 있으면 이진 탐색으로 범위의 양 끝을 찾을 수 있다. 아래 bisect_left는 4 이상인 첫 위치, bisect_right는 4보다 큰 첫 위치를 찾는다. [1,4,4,4,9]에서 결과는 1과 4이므로 4는 세 개다.
검색은 로그 비교로 가능하지만 배열 가운데에 삽입하면 뒤 원소 이동이 필요하다. bisect로 삽입 위치를 빨리 찾았다고 전체 삽입이 O(log n)이 되는 것은 아니다. 정적인 목록에 많은 조회가 있을 때와 빈번한 삽입·삭제가 있을 때의 선택이 다르다.
범위 결과를 실제로 복사해서 반환하면 결과 원소 수만큼 비용이 든다. 경계 두 개만 반환하는 함수와 모든 원소를 반환하는 함수의 시간·공간을 구분한다. 원본이 이후 변경될 수 있다면 경계 인덱스가 계속 유효한지도 고려해야 한다.
같은 비교 기준으로 정렬하고 검색해야 한다. 문자열을 소문자 키로 정렬한 뒤 원본 문자열의 다른 기준으로 탐색하면 경계가 맞지 않을 수 있다. 비교 키를 미리 계산하는 방식은 반복 비용을 줄이지만 키와 원본의 동기화가 필요하다.
예제 코드
from bisect import bisect_left, bisect_right
values = [1, 4, 4, 4, 9]
left = bisect_left(values, 4)
right = bisect_right(values, 4)
print(left, right)
print(right - left)
print(values[left:right])실행 결과
1 4
3
[4, 4, 4]힙: 최솟값을 반복해서 꺼내기
최소 힙은 부모의 값이 자식보다 크지 않다는 규칙을 유지한다. 전체가 정렬된 배열은 아니지만 루트에서 최솟값을 얻을 수 있다. 이진 힙은 배열 인덱스로 부모와 자식 관계를 표현해 명시적 노드 포인터 없이 구현할 수 있다.
아래 heapify로 목록을 힙으로 바꾸고 3을 추가한 뒤 반복해서 꺼내면 2,3,5,7 순서다. 힙 배열을 그대로 순회한 결과가 정렬 순서라고 가정하면 안 된다. 정렬된 출력이 필요하면 꺼내는 연산을 반복하거나 별도 정렬을 해야 한다.
이진 힙의 삽입과 최솟값 제거는 일반적으로 O(log n), 루트 조회는 O(1)이다. 전체 배열을 바닥부터 힙으로 만드는 heapify는 선형 시간으로 구현할 수 있다. 원소를 하나씩 삽입하는 것과 같은 비용이라고 단정하지 않는다.
힙은 임의의 특정 항목을 찾아 갱신하는 데 자동으로 효율적인 구조는 아니다. 우선순위 변경이 잦으면 항목 위치를 추적하는 인덱스나 오래된 항목을 무시하는 전략이 필요할 수 있다. 최소 후보를 고르는 기능과 키 기반 검색 기능을 구분한다.
예제 코드
import heapq
heap = [7, 2, 5]
heapq.heapify(heap)
heapq.heappush(heap, 3)
result = []
while heap:
result.append(heapq.heappop(heap))
print(result)실행 결과
[2, 3, 5, 7]우선순위 큐의 동점 처리
우선순위와 작업 객체를 튜플로 힙에 넣으면 우선순위가 같을 때 다음 필드도 비교할 수 있다. 작업 객체가 사전처럼 순서 비교를 지원하지 않으면 TypeError가 날 수 있다. 숫자 우선순위만 정하면 모든 경우가 해결된다고 생각하기 쉬운 지점이다.
아래는 같은 우선순위의 사전 두 개를 넣어 의도한 실패를 확인한다. 실패한 힙은 계속 사용하지 않고 새로 만든다. 수정한 버전은 증가하는 순번을 두 번째 필드에 넣어 동점을 해결한다. 작업 객체 자체를 비교하지 않으며 A가 B보다 먼저 들어왔으므로 A,B 순서로 나온다.
순번은 동점의 선입선출 규칙을 명시하는 방법이다. 다른 정책이 필요하면 마감 시간이나 별도 키를 사용한다. 변경 중 실패가 발생한 컨테이너의 상태가 항상 이전과 같다고 가정하지 말고 라이브러리의 예외 보장을 확인한다.
작업 취소나 우선순위 변경에는 별도 식별자와 유효성 검사가 필요할 수 있다. 오래된 항목을 힙에 남기고 꺼낼 때 무시하는 방식은 간단하지만 오래된 데이터가 쌓일 수 있어 정리 정책도 필요하다.
예제 코드
import heapq
from itertools import count
broken = []
try:
heapq.heappush(broken, (1, {'name': 'A'}))
heapq.heappush(broken, (1, {'name': 'B'}))
except TypeError:
print('TypeError')
queue = []
sequence = count()
for name in ['A', 'B']:
heapq.heappush(queue, (1, next(sequence), {'name': name}))
print([heapq.heappop(queue)[2]['name'] for _ in range(2)])실행 결과
TypeError
['A', 'B']그래프의 인접 목록과 행렬
그래프 자료 구조는 정점과 간선을 저장한다. 인접 목록은 각 정점의 이웃만 모으고, 인접 행렬은 정점 쌍마다 연결 정보를 저장한다. 희소 그래프에서는 목록이 공간을 줄일 수 있고, 작은 조밀 그래프나 연결 여부의 빠른 접근에는 행렬이 단순할 수 있다.
아래 무방향 그래프는 A-B와 B-C를 양쪽 목록에 넣는다. A의 이웃은 B, B의 이웃은 A,C다. 한쪽만 넣으면 방향 그래프처럼 동작하게 된다. 고립 정점도 키로 등록해야 모든 정점을 빠뜨리지 않는다.
인접 목록을 배열로 둘지 집합으로 둘지도 연산에 영향을 준다. 목록은 순서와 중복을 보존하지만 특정 이웃 존재 검사가 선형일 수 있다. 집합은 포함 검사에 유리할 수 있지만 순서와 다중 간선 정보를 잃는다. 같은 두 정점 사이의 여러 간선을 허용하는 모델이면 별도 표현이 필요하다.
간선 가중치, 방향, 자기 자신으로의 간선, 삭제 정책을 명세한다. 정점을 삭제할 때 들어오는 간선까지 정리할지, 반대 방향 인덱스를 유지할지에 따라 비용이 달라진다. 그래프 알고리즘의 O(V+E) 설명은 이런 표현과 순회 비용을 전제로 한다.
예제 코드
graph = {name: [] for name in ['A', 'B', 'C', 'X']}
for left, right in [('A', 'B'), ('B', 'C')]:
graph[left].append(right)
graph[right].append(left)
print(graph['A'])
print(graph['B'])
print(graph['X'])실행 결과
['B']
['A', 'C']
[]디스크용 구조와 메모리용 구조
메모리 안에서 포인터를 한 번 따라가는 비용과 디스크나 원격 저장소의 블록을 읽는 비용은 다르다. 외부 메모리 자료 구조는 블록 단위 전송을 줄이는 것이 중요한 설계 목표다. 이진 트리의 높이만 작게 만드는 것보다 한 블록에서 많은 키를 비교하는 구조가 유리할 수 있다.
B-트리 계열은 여러 키와 자식을 한 노드에 두는 방식으로 저장 장치의 블록 접근을 고려한다. 데이터베이스 인덱스에서 순서 있는 검색과 범위 조회를 지원하는 배경을 이해하는 데 도움이 된다. 다만 실제 DBMS의 페이지 형식과 동시성, 로그·복구 정책은 제품별 구현이다.
메모리에 들어갈 때 빠른 구조가 디스크에서도 같은 성능을 내는 것은 아니다. 직렬화 크기, 페이지 분할, 캐시 적중률, 쓰기 증폭과 장애 후 복구를 함께 고려한다. 인메모리 예제의 단순 포인터 연결을 파일에 그대로 저장하는 것은 주소와 수명 문제 때문에 별도 설계가 필요하다.
영속 자료 구조라는 용어도 문맥을 확인한다. 이전 버전을 보존하는 함수형 자료 구조와, 전원이 꺼져도 저장 장치에 남는 내구성은 다른 개념으로 사용된다. 버전 공유 구조가 있다고 자동으로 디스크 장애 복구가 보장되는 것은 아니다.
불변 구조와 구조 공유
불변 구조는 생성한 값을 직접 바꾸지 않고 변경된 새 값을 만든다. 이전 버전을 보관하거나 여러 코드가 같은 값을 안전하게 읽는 설계에 도움이 될 수 있다. 그러나 매번 전체 데이터를 복사하면 비용이 커질 수 있어 변경 경로만 새로 만들고 나머지를 공유하는 방식이 사용된다.
구조 공유는 공유하는 부분을 변경하지 않는다는 계약과 함께 작동한다. 바깥 객체만 새로 만든 뒤 안쪽 목록을 변경하면 이전 버전도 바뀔 수 있다. 앞의 얕은 복사 예제와 연결되는 문제다. 어떤 계층이 불변이고 어떤 참조가 공유되는지 명확히 한다.
불변 컬렉션이 외부 자원의 동작까지 불변으로 만드는 것은 아니다. 내부 원소가 파일 연결이나 변경 가능한 객체라면 그 객체의 상태는 별도로 바뀔 수 있다. 언어의 타입 제한, 라이브러리 계약과 실제 데이터 수명을 함께 보아야 한다.
불변 설계는 변경 추적과 테스트를 쉽게 만들 수 있지만 메모리 압력과 할당, 오래된 버전의 보관 비용이 있다. 모든 상황에 같은 전략을 적용하기보다 읽기·쓰기 비율, 동시성 요구와 버전 수명을 기준으로 선택한다.
실전 예제: LRU 캐시의 두 가지 요구
LRU 캐시는 최근 사용한 항목을 유지하고 용량을 넘으면 가장 오래 사용하지 않은 항목을 제거한다. 빠른 키 조회와 최근 사용 순서 갱신이라는 두 요구가 함께 있다. 해시 맵과 연결 순서 같은 구조를 결합하거나 그 기능을 제공하는 라이브러리를 사용할 수 있다.
아래는 OrderedDict로 작은 캐시를 구현한다. get은 조회한 항목을 끝으로 옮겨 가장 최근 사용으로 표시한다. put도 새 값이나 갱신한 값을 끝으로 옮기고 용량을 넘으면 맨 앞을 제거한다. 단순 삽입 순서만 유지하면 최근 조회를 반영하지 못해 LRU가 아니라 다른 정책이 된다.
용량 2에서 A,B를 넣고 A를 읽으면 순서는 B,A가 된다. C를 넣으면 B가 제거되고 A,C가 남는다. 출력은 1과 A,C 목록, B missing이다. 값으로 None을 저장할 수도 있으므로 없는 키는 KeyError로 구분한다.
이 예제의 용량은 항목 개수다. 항목 하나가 매우 큰 객체일 수 있으므로 실제 바이트 제한을 보장하지 않는다. 만료 시간, 동시 접근, 계산 중인 값의 중복 요청과 영속성도 구현하지 않았다. 운영 캐시에서는 이런 정책을 별도로 결정해야 한다.
캐시가 데이터를 진실의 원본으로 대체하는지 여부도 중요하다. 재계산 가능한 값과 유일한 사용자 자료를 같은 축출 정책으로 다루면 안 된다. 캐시는 빠른 조회를 위한 보조 구조인지, 제거해도 되는 데이터인지 명확히 하고 원본 갱신 시 무효화 정책을 설계한다.
예제 코드
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
if not isinstance(capacity, int) or isinstance(capacity, bool) or capacity <= 0:
raise ValueError('positive integer capacity required')
self.capacity = capacity
self.items = OrderedDict()
def get(self, key):
if key not in self.items:
raise KeyError(key)
self.items.move_to_end(key)
return self.items[key]
def put(self, key, value):
self.items[key] = value
self.items.move_to_end(key)
if len(self.items) > self.capacity:
self.items.popitem(last=False)
cache = LRUCache(2)
cache.put('A', 1)
cache.put('B', 2)
print(cache.get('A'))
cache.put('C', 3)
print(list(cache.items))
try:
cache.get('B')
except KeyError:
print('B missing')실행 결과
1
['A', 'C']
B missing자료 구조의 불변식을 테스트하기
컨테이너 테스트는 한 번 넣고 한 번 꺼내는 예제만으로 충분하지 않다. 빈 상태에서 시작하고, 한 항목에서 여러 항목으로 늘고, 다시 비어지는 전이를 확인한다. 같은 키 갱신, 중복 입력, 용량 초과와 없는 항목 접근도 계약에 따라 검사한다.
아래 코드는 앞의 balanced와 LRUCache 정의 뒤에 붙여 실행한다. 괄호의 정상·오류·빈 입력을 확인하고, 캐시에서는 최근 조회가 축출 순서에 반영되는지, 기존 키 갱신이 개수를 늘리지 않는지, 용량 초과와 잘못된 용량이 처리되는지 검사한다. 총 10개 조건을 확인한다.
내부 표현을 직접 검사하는 항목은 불변식 확인에 유용하지만 공개 동작 테스트와 구분한다. 구현을 바꿀 때 내부 순서 표현은 달라질 수 있어도 최근 사용 정책과 반환값은 유지되어야 한다. 외부 사용자가 관찰하는 계약을 중심으로 테스트하면 리팩터링에 덜 민감하다.
복잡한 자료 구조는 무작위 연산열을 단순한 기준 모델과 비교하는 방식도 사용할 수 있다. 실패한 연산열을 기록하고 작은 재현으로 줄이면 삽입·삭제 조합에서만 발생하는 오류를 찾기 쉽다. 테스트를 통과했다는 사실과 모든 연산열의 증명은 구분하되 둘을 함께 사용한다.
예제 코드
assert balanced('([])')
assert not balanced('([)]')
assert balanced('')
cache = LRUCache(2)
cache.put('A', 1)
cache.put('B', 2)
assert cache.get('A') == 1
cache.put('C', 3)
assert list(cache.items) == ['A', 'C']
assert 'B' not in cache.items
cache.put('A', 9)
assert cache.get('A') == 9
assert len(cache.items) == 2
cache.put('D', 4)
assert 'C' not in cache.items
try:
LRUCache(0)
except ValueError:
pass
else:
raise AssertionError('invalid capacity accepted')
print('10 checks passed')실행 결과
10 checks passed동시성: 안전한 개별 연산과 안전한 절차
어떤 컨테이너의 개별 연산이 특정 환경에서 안전하더라도 여러 연산을 묶은 절차가 원자적이라는 뜻은 아니다. “키가 없으면 값을 계산해 넣기” 사이에 다른 실행 흐름이 같은 작업을 할 수 있다. 확인과 변경의 경계를 어떻게 보호하는지 설계해야 한다.
스레드 사이 작업 전달에는 동기화 기능을 제공하는 큐를 검토할 수 있다. 하지만 큐에 넣었다는 사실이 작업 완료를 뜻하지는 않는다. 소비 실패, 재시도, 종료 신호와 완료 추적은 별도 계약이다. 데이터베이스 트랜잭션이나 분산 메시지 큐의 보장을 메모리 컨테이너에 기대하지 않는다.
잠금을 사용할 때는 보호할 불변식과 범위를 정한다. 너무 넓으면 병렬성이 줄고, 너무 좁으면 여러 구조의 상태가 어긋날 수 있다. 캐시의 사전과 최근 사용 순서를 별도 구조로 유지한다면 둘의 변경을 일관되게 처리해야 한다.
lock-free나 wait-free 같은 용어는 특정 진행 보장과 알고리즘의 성질을 말한다. 단순히 잠금 호출이 보이지 않는 코드에 붙이지 않는다. 언어 런타임과 메모리 모델, 원자적 연산을 이해해야 하므로 단일 스레드 자료 구조 학습과 분리해서 다루는 것이 좋다.
메모리 사용과 지역성
원소 수가 같아도 자료 구조의 메모리 사용은 다르다. 포인터, 해시 슬롯의 여유 공간, 객체 헤더와 할당 단위가 추가된다. 작은 정수 몇 개를 개별 객체와 노드로 보관하는 것과 조밀한 배열로 보관하는 것은 큰 차이가 날 수 있다.
연속된 자료를 순서대로 읽는 패턴은 캐시 지역성에서 이점을 얻을 수 있다. 연결 노드를 여러 곳에서 찾아가는 패턴은 같은 O(n) 순회라도 실제 지연이 다를 수 있다. 반대로 배열 가운데 변경이 많으면 원소 이동이 부담된다. 점근 복잡도와 하드웨어 동작을 함께 보아야 한다.
메모리 측정에서는 컨테이너 객체 자체 크기와 내부가 참조하는 전체 객체 크기를 구분한다. 같은 객체를 여러 컨테이너가 공유하면 단순 합산이 중복 계산할 수 있고, 얕은 크기만 재면 실제 보유 자료를 놓칠 수 있다. 측정 도구의 포함 범위를 확인한다.
자료형을 좁히거나 직렬화해 저장하면 공간을 줄일 수 있지만 변환 비용과 표현 범위, 정밀도 문제가 생긴다. 메모리가 부족한 상황에서 단순히 캐시를 늘리는 선택은 전체 시스템을 더 느리게 만들 수 있다. 실제 작업량과 메모리 상한을 기준으로 판단한다.
연산 중심으로 선택하기
먼저 가장 자주 하는 연산을 적는다. 위치로 읽는지, 키로 찾는지, 앞에서 꺼내는지, 최솟값을 반복해서 고르는지, 범위 내 값을 순회하는지에 따라 후보가 달라진다. 삽입·삭제·검색의 비율과 원소 수, 자료가 고정되어 있는지도 중요하다.
고정된 순서 자료의 임의 접근에는 배열을, 마지막 작업부터 처리할 때는 스택을, 도착 순서를 유지할 때는 큐를 검토한다. 존재 여부에는 집합, 키별 값에는 맵, 순서 있는 범위 검색에는 정렬 배열이나 균형 트리를 비교한다. 최솟값 선택에는 힙이 유용하지만 임의 키 검색까지 대신하지는 않는다.
하나의 구조로 모든 요구를 해결할 필요는 없다. 검색용 사전과 표시 순서 목록을 함께 둘 수 있지만 변경 시 두 구조가 일치해야 한다는 새로운 불변식이 생긴다. 중복 저장의 비용과 유지 책임을 고려하고, 라이브러리가 이미 제공하는 복합 구조가 있는지도 확인한다.
선택을 설명할 때는 “이 구조가 가장 빠르다”보다 어떤 연산에서 어떤 전제 아래 어떤 비용을 제공하는지 적는다. 작은 입력에서는 단순한 구현이 충분할 수 있고, 복잡한 최적화는 실제 병목이 확인됐을 때 도입하는 것이 낫다. 정확한 계약, 검증 가능한 불변식과 유지보수 가능성을 함께 평가한다.