자료구조Data Structures
데이터 항목을 앞뒤 · 부모 자식 · 임의 연결 · 키 대응 가운데 어떤 관계로 놓고 어떤 연산을 싸게 할지 정하는 방식이다. 스택 · 큐 · 연결 리스트 · 트리 · 힙 · 그래프 · 해시 테이블을 다루고, 그 위에서 도는 정렬 · 경로 절차는 그래프 알고리즘이 맡는다.
1요약
- 자료구조는 알고리즘에서 데이터를 어떤 관계 모양으로 놓는가를 맡아 선형(스택 · 큐 · 연결 리스트) · 계층(트리 · 힙) · 망(그래프) · 키 대응(해시 테이블) 네 모양을 묶고, 정렬 · 최단 경로 같은 절차는 그 위에서 돈다.
- 구조를 잘못 고르면 같은 연산이 n 배로 든다 — Python list 의 맨 앞 꺼내기는 남은 항목을 모두 옮기므로(Python collections) 10만 건 대기열을 앞에서 다 꺼내면 이동이 약 50억 번이고, deque 는 꺼낼 때마다 상수 비용이다(직접 계산).
- 「자료가 많아지니 느리다」는 가장 자주 하는 연산이 무엇인가로 가른다 — 끝에서 넣고 빼면 스택 · 큐, 키로 찾으면 해시 테이블, 가장 급한 것을 거듭 꺼내면 힙, 범위로 찾으면 트리 쪽이다.
2등장 배경
1950년대 프로그램은 데이터를 고정 주소의 배열에 두었고, 중간에 항목 하나를 끼우려면 뒤쪽을 모두 밀어야 했다. 1957년 Newell · Shaw 는 정리 증명 프로그램을 위해 노드마다 다음 노드의 주소를 둔 리스트 언어 IPL 을 발표했다(Newell · Shaw 1957).
1964년 Williams 는 부모가 자식보다 작거나 같다는 규칙 하나로 배열을 트리처럼 쓰는 힙을 냈고(Williams 1964), 1968년 Knuth 는 TAOCP Volume 1 에서 스택 · 큐 · 리스트 · 트리를 «정보 구조» 한 장으로 묶었다(Knuth TAOCP). 1974년 Liskov · Zilles 는 구조를 «쓸 수 있는 연산의 약속»으로 정의하고 내부 구현을 숨기는 추상 자료형을 제안했다(Liskov · Zilles 1974).
지금은 deque · heapq · OrderedDict 처럼 표준 라이브러리가 구현을 주므로(Python collections) 실무의 일은 구조를 짜는 것보다 연산 약속에 맞는 구조를 고르는 것이 됐다. NIST 도 자료구조를 구현과 무관한 «값과 연산의 집합»으로 정의한다(NIST DADS abstract data type).
3쉽게 이해하기 — 식당 주방의 일곱 가지 정리법
식당 주방장 민 씨는 들어온 주문표를 레일에 차례로 꽂고, 급한 주문은 종을 울려 먼저 만든다. 메뉴판 분류(식사 › 면 › 냉면)를 따라 레시피 카드를 찾고, 고리로 이은 카드를 한 장씩 넘기며 요리한다. 접시는 더미 맨 위부터 꺼내고, 포장은 손님 번호가 적힌 보관함에 바로 넣으며, 배달은 가게와 집을 잇는 길 지도로 고른다.
그림 1 · 주방장 민 씨는 주문을 받아 배달까지 가는 동안 물건마다 다른 정리법을 쓰고, 정리법마다 실제 자료구조 하나가 짝을 이룬다.
그림 2 · 같은 주문 넷을 넣어도 레일은 들어온 순서로, 급한 종은 급한 정도로 내보낸다 — 큐와 우선순위 큐의 경계는 «무엇이 꺼낼 순서를 정하나» 하나다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 주방장 민 씨 | 알고리즘 | 자료구조가 주는 연산을 불러 일을 끝까지 처리한다 |
| 주문 레일 | 스택 · 큐(큐) | 먼저 넣은 항목을 먼저 꺼낸다 |
| 급한 종 | 힙 · 우선순위 큐 | 우선순위가 가장 높은 항목을 늘 맨 앞에 둔다 |
| 메뉴판 분류 | 트리 | 뿌리에서 갈라지는 부모 자식 관계로 항목을 찾는다 |
| 고리 카드 | 연결 리스트 | 노드마다 다음 노드를 가리키는 링크로 잇는다 |
| 접시 더미 | 스택 · 큐(스택) | 마지막에 넣은 항목만 꺼낸다 |
| 번호 보관함 | 해시 테이블 | 키를 해시 함수로 버킷 번호로 바꿔 바로 연다 |
| 배달 지도 | 그래프 | 정점과 간선으로 제약 없는 연결을 적는다 |
⚠ 비유가 맞지 않는 곳: 주방에서는 물건마다 정리법이 하나지만, 실제로는 한 데이터를 두 구조에 함께 담는 일이 흔하다(동작 절의 해시 테이블 + 연결 리스트). 보관함도 실제로는 두 키가 같은 버킷에 떨어지는 충돌이 생긴다.
4구조 — 네 관계 모양과 여섯 토픽
아래 토픽 여섯은 «항목 사이 관계가 어떤 모양인가»로 나뉜다. 모양이 단순할수록 연산이 적고 싸며, 모양이 자유로울수록 표현은 넓지만 정해진 순서가 없다.
| 하위 토픽 | 관계 모양 | 지키는 규칙 | 바탕 부품 | 근거 |
|---|---|---|---|---|
| 스택 · 큐 | 선형 | 가장 최근 것만(스택) · 가장 오래된 것만(큐) 꺼냄 | 배열 · 연결 리스트 | NIST DADS stack |
| 연결 리스트 | 선형 | 노드마다 다음 노드 링크 · 머리 포인터로 들어감 | 노드 · 링크 | NIST DADS linked list |
| 트리 | 계층 | 뿌리 하나 · 사이클 없는 연결 | 노드 · 자식 링크 | NIST DADS tree |
| 힙 · 우선순위 큐 | 계층 | 부모 ≤ 자식 · 최소가 뿌리 | 완전 이진 트리를 배열에 | Python heapq |
| 그래프 | 망 | 정점 쌍 사이 간선 · 모양 제약 없음 | 인접 리스트 · 인접 행렬 | NIST DADS graph |
| 해시 테이블 | 키 대응 | 해시 함수로 키 → 버킷 번호 · 충돌 처리 | 배열 + 버킷 | NIST DADS hash table |
그림 3 · 연결 리스트는 큐 · 해시 버킷의 부품이 되고, 트리는 사이클 없는 그래프, 힙은 규칙이 붙은 트리라서 여섯 토픽은 «부품»과 «특수한 경우» 두 관계로 이어진다.
정렬 · 탐색 순서는 그래프 알고리즘, 분할 정복 · 동적 계획법은 알고리즘 설계 기법, 비용 표기는 알고리즘 분석이 맡는다. 자료구조는 «항목을 어떤 관계로 담고 연산 하나가 얼마인가»까지만 다룬다.
🔑 자료구조를 고르는 것은 «어느 연산을 싸게 하고 어느 연산을 비싸게 둘지»를 고르는 것이다 — 관계 모양이 좁을수록 싼 연산은 적어지지만 그 연산은 더 싸진다.
5동작 — 용량 3 LRU 캐시의 해시 테이블 · 연결 리스트 협업
가장 오래 쓰지 않은 항목을 내보내는 LRU 캐시는 «키로 찾기»와 «가장 오래된 것 꺼내기»를 함께 싸게 해야 해서 두 토픽을 묶어 쓴다. Python 3.15 OrderedDict 가 이 짝으로 구현돼 있다(CPython OrderedDict). 용량 3 · 키 a ~ d 는 설명용 가정 값이다.
- 빈 캐시 = 해시 테이블(키 → 노드 위치) + 원형 이중 연결 리스트(머리 쪽 = 가장 오래 안 씀 · 꼬리 쪽 = 최근)와 지우지 않는 감시 노드 하나다(CPython OrderedDict).
- a · b · c 를 넣는다 — 표에 키 3개, 리스트는 감시 ⇄ a ⇄ b ⇄ c 다.
- a 를 읽는다 — 표에서 a 노드를 평균 상수 시간에 찾고(NIST DADS hash table), 이웃 두 링크를 이어 떼어 낸 뒤 꼬리에 링크 네 개로 붙인다(포인터 6개 · 직접 계산). 리스트는 b ⇄ c ⇄ a 다(move_to_end · Python collections).
- d 를 넣는다 — 표의 키가 4개로 용량을 넘는다.
- 머리 쪽 첫 노드 b 를 떼어 내고 표에서도 지운다(popitem(last=False) · Python collections). 리스트는 c ⇄ a ⇄ d 로 키 3개가 남는다.
- 리스트만 썼다면 3단계의 a 찾기에 최대 n 개 노드를 훑고, 표만 썼다면 5단계의 «가장 오래된 키»를 알려고 전부 훑는다. 둘을 묶어 모든 연산이 dict 와 같은 차수가 된다(CPython OrderedDict).
그림 4 · 읽힌 a 는 꼬리로 옮겨지고, 넘친 때는 머리 쪽 b 가 나가며, 해시 테이블은 «어디 있나»를, 연결 리스트는 «얼마나 오래됐나»를 맡는다.
그림 5 · 모든 열이 상수인 행은 없다 — 구조를 고르는 일은 가장 자주 하는 연산의 열에서 상수 · 로그 셀을 가진 행을 찾는 일이다.
🔑 한 구조로 모든 연산이 싸지지 않으면 구조 둘을 겹쳐 쓴다 — LRU 캐시처럼 해시 테이블이 «어디 있나»를, 연결 리스트가 «순서»를 맡으면 두 약속을 함께 지킨다.
6비교 — 관련 기술과의 경계
| 기술 | 맡는 일 | 경계 | 넘기는 곳 |
|---|---|---|---|
| 자료구조 | 항목의 관계 모양 · 연산 하나의 비용 | 연산의 약속과 구현까지 | 연산을 엮는 순서 → 그래프 알고리즘 · 설계 기법 |
| 그래프 알고리즘 | 정렬 · BFS · DFS · 최단 경로 · MST | 구조를 받아 문제를 푸는 절차 | 큐 · 힙 · 인접 리스트 → 자료구조 |
| 알고리즘 설계 기법 | 분할 정복 · 동적 계획법 · 그리디 | 문제를 쪼개고 고르는 틀 | 부분 답을 담을 표 · 힙 → 자료구조 |
| 알고리즘 분석 | 증가 차수 · 시간 · 공간 복잡도 | 비용을 재는 잣대 | 잴 연산의 정의 → 자료구조 |
| B-Tree(데이터베이스) | 디스크 페이지 단위 색인 | 저장 장치 접근 수를 줄이는 트리 | 메모리 안 트리 원리 → 자료구조 |
분석«항목을 무엇으로 담고 연산 하나가 얼마인가»는 자료구조에서, «그 연산을 어떤 순서로 몇 번 부르나»는 그래프 알고리즘 · 설계 기법에서, 「얼마」를 적는 표기는 알고리즘 분석에서 본다. 근거는 NIST 의 추상 자료형 정의 — 구조는 값과 연산의 약속이고 그 약속을 쓰는 절차와 따로 정의된다(NIST DADS abstract data type).
7실무 진단 — 느림 · 틀림을 하위 토픽으로 가르기
분석먼저 «결과가 틀린가»(내보낸 항목 · 꺼낸 순서)를 보고, 맞는데 느리면 가장 자주 부르는 연산이 그 구조에서 선형 셀인지 그림 5 로 대조한다. 틀린 결과는 구조의 규칙(heap 불변식 · LRU 순서)이 깨졌다는 뜻이라 속도보다 먼저 고친다(Python heapq · Python collections).
| # | 증상 | 의심 원인 | 하위 토픽 | 확인 자료 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 우선순위 작업이 들어온 순서대로 나감 | 힙에 heappush 대신 append 로 넣음 | 힙 · 우선순위 큐 | 모든 k 에서 heap[k] <= heap[2*k+1] 검사 | 하나라도 거짓이면 불변식 깨짐(Python heapq) |
| 2 | 캐시가 방금 쓴 항목을 내보냄 | 적중 때 꼬리로 옮기지 않음 | 연결 리스트 | 적중 경로의 move_to_end 호출 여부 | 호출 없으면 넣은 순서 = 내보낼 순서(Python collections) |
| 3 | 대기열이 길수록 꺼내기가 느려짐 | list 앞쪽에서 pop(0) · insert(0, v) | 스택 · 큐 | 코드에서 두 호출 찾기 | 있으면 매번 O(n) 이동 → deque(Python collections) |
| 4 | 키 찾기가 가끔 크게 느려짐 | 키가 한 버킷에 몰리는 충돌 | 해시 테이블 | 키마다 hash(k) % 버킷 수 분포 세기 | 한 버킷에 몰리면 해시 함수 · 충돌 처리 탓(NIST DADS hash table) |
1 · 2행은 결과가 틀린 문제라 3 · 4행 측정보다 먼저 끝낸다.
8시험 대비
www.q-net.or.kr시험에서는 자료구조의 분류(선형 · 비선형)와 각 구조의 특징 · 연산을 묻는 정의 · 특징형, 또는 스택 · 큐 · 힙에 값을 넣고 빼는 과정을 묻는 동작 · 절차 설명형으로 나올 수 있다. 어느 쪽이든 «관계 모양 → 지키는 규칙 → 싼 연산 · 비싼 연산» 순서를 먼저 세우고 묻는 구조를 그 위치에 놓는다.
- 개요 — 정의(값 + 연산의 약속 · NIST DADS abstract data type) · 추상 자료형과 구현의 분리(1974)
- 분류 — 그림 3 하위 토픽 지도(선형 · 계층 · 망 · 키 대응) + 하위 토픽 표(규칙 · 바탕 부품)
- 연산 비용 — 그림 5 구조 × 연산 표(상수 · 로그 · 선형)
- 동작 예 — 그림 4 LRU 캐시(해시 테이블 + 이중 연결 리스트 · 포인터 6개)
- 선택 기준 — 가장 자주 하는 연산 · 순서 필요 여부 · 범위 질의 여부
- 응용 — 호출 스택 · 작업 대기열 · 스케줄러 힙 · 색인 트리 · 길 찾기의 인접 리스트
꼭 쓸 키워드
추상 자료형LIFOFIFO이중 연결 리스트완전 이진 트리힙 불변식인접 리스트해시 충돌버킷LRU
다른 답안과 차이를 내는 한 가지는 그림 5 처럼 «구조 × 연산» 표를 그려 어느 연산이 싸고 비싼지를 한눈에 보이고, 두 구조를 겹쳐 쓰는 LRU 예를 붙이는 것이다.
9오해와 사실
- 오해해시 테이블이 늘 트리보다 낫다.사실해시 테이블은 키 순서가 없어 범위 찾기가 전체 훑기이고, 균형 탐색 트리는 O(log n + k) 로 범위를 꺼낸다(그림 5 · NIST DADS hash table).
- 오해힙은 정렬된 배열이다.사실힙은 부모와 자식 사이 규칙(
heap[k] <= heap[2*k+1])만 지키므로 형제끼리는 순서가 없고, 최소가heap[0]이라는 것만 보장한다(Python heapq). - 오해연결 리스트는 넣기 · 빼기가 언제나 O(1) 이다.사실노드 위치를 알 때만 그렇고, 위치를 찾는 데는 선형 탐색이 든다(NIST DADS linked list) — LRU 캐시가 해시 테이블을 붙이는 까닭이다.
10핵심 정리
| 하위 토픽 | 싼 연산 | 비싼 연산 | 대표 쓰임 | Python 구현 |
|---|---|---|---|---|
| 스택 · 큐 | 끝에서 넣기 · 꺼내기 | 키로 찾기 | 호출 기록 · 작업 대기열 | list 끝 · collections.deque |
| 연결 리스트 | 위치 아는 노드의 넣기 · 떼기 | 위치 찾기 | LRU 순서 · 해시 버킷 | OrderedDict 안 이중 리스트 |
| 트리 | 범위 · 순서 찾기 | 균형이 깨진 때의 탐색 | 분류 · 색인 · 파일 체계 | 표준 모듈 없음(직접 구현) |
| 힙 · 우선순위 큐 | 최소 보기 · 꺼내기 | 임의 키 찾기 | 스케줄러 · 다익스트라 | heapq |
| 그래프 | 이웃 정점 훑기(인접 리스트) | 모든 쌍 연결 확인 | 경로 · 의존 관계 | dict 의 이웃 목록 |
| 해시 테이블 | 키로 넣기 · 찾기 | 순서 · 범위 | 캐시 · 중복 제거 | dict · set |
11참고 문헌
- 먼저 볼 문헌
- ★ Dictionary of Algorithms and Data Structures - abstract data type (Paul E. Black ed.) — 자료구조를 구현과 떼어 «값 + 연산의 약속»으로 정의하는 공공 정의를 볼 때
- ★ Dictionary of Algorithms and Data Structures - linked list — 연결 리스트가 큐 · 스택 · 해시 버킷의 부품이 되는 관계를 볼 때
- ★ collections - Container datatypes (Python 3.15 documentation) — deque 와 list 의 앞쪽 연산 비용 · OrderedDict 의 move_to_end · popitem 을 볼 때
- ★ heapq - Heap queue algorithm (Python 3.15 documentation) — 배열에 담은 힙의 불변식(heap[k] <= heap[2*k+1])을 볼 때
- 본문 근거
- Dictionary of Algorithms and Data Structures - stack — NIST · 2019-10 ·
xlinux.nist.gov/dads/HTML/stack.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - tree — NIST · 2017-12 ·
xlinux.nist.gov/dads/HTML/tree.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - heap — NIST · 2023-04 ·
xlinux.nist.gov/dads/HTML/heap.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - priority queue — NIST · 2021-11 ·
xlinux.nist.gov/dads/HTML/priorityque.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - graph — NIST · 2022-07 ·
xlinux.nist.gov/dads/HTML/graph.html· 확인 2026-11-14 - Dictionary of Algorithms and Data Structures - hash table — NIST · 2022-04 ·
xlinux.nist.gov/dads/HTML/hashtab.html· 확인 2026-11-14 - CPython source Lib/collections/__init__.py (OrderedDict) — Python Software Foundation · 2026-11 ·
github.com/python/cpython/blob/main/Lib/collections/__init__.py· 확인 2026-11-14 - Programming the Logic Theory Machine (Proc. Western Joint Computer Conference pp. 230-240) — A. Newell · J. C. Shaw · 1957-02 ·
doi.org/10.1145/1455567.1455606· 확인 2026-11-14 - Algorithm 232 Heapsort (Communications of the ACM 7(6) pp. 347-348) — J. W. J. Williams · 1964-06 ·
doi.org/10.1145/512274.512284· 확인 2026-11-14 - Programming with Abstract Data Types (ACM SIGPLAN Notices 9(4) pp. 50-59) — Barbara Liskov · Stephen Zilles · 1974-04 ·
doi.org/10.1145/942572.807045· 확인 2026-11-14 - The Art of Computer Programming (Volume 1 Fundamental Algorithms Third Edition 1997) — D. E. Knuth · Addison-Wesley · 2026-11 ·
www-cs-faculty.stanford.edu/~knuth/taocp.html· 확인 2026-11-14