IT › 컴퓨터 시스템 › 알고리즘

자료구조Data Structures

데이터 항목을 앞뒤 · 부모 자식 · 임의 연결 · 키 대응 가운데 어떤 관계로 놓고 어떤 연산을 싸게 할지 정하는 방식이다. 스택 · 큐 · 연결 리스트 · 트리 · 힙 · 그래프 · 해시 테이블을 다루고, 그 위에서 도는 정렬 · 경로 절차는 그래프 알고리즘이 맡는다.

1요약

  1. 자료구조는 알고리즘에서 데이터를 어떤 관계 모양으로 놓는가를 맡아 선형(스택 · 큐 · 연결 리스트) · 계층(트리 · 힙) · 망(그래프) · 키 대응(해시 테이블) 네 모양을 묶고, 정렬 · 최단 경로 같은 절차는 그 위에서 돈다.
  2. 구조를 잘못 고르면 같은 연산이 n 배로 든다 — Python list 의 맨 앞 꺼내기는 남은 항목을 모두 옮기므로(Python collections) 10만 건 대기열을 앞에서 다 꺼내면 이동이 약 50억 번이고, deque 는 꺼낼 때마다 상수 비용이다(직접 계산).
  3. 「자료가 많아지니 느리다」는 가장 자주 하는 연산이 무엇인가로 가른다 — 끝에서 넣고 빼면 스택 · 큐, 키로 찾으면 해시 테이블, 가장 급한 것을 거듭 꺼내면 힙, 범위로 찾으면 트리 쪽이다.

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 우선순위 큐 · 힙 가장 급한 것 먼저 메뉴판 3 트리 · 분류 식사 › 면 › 냉면 고리 카드 4 연결 리스트 다음 카드로 넘김 접시 더미 5 스택 · 맨 위 마지막에 쌓은 것부터 번호 보관함 6 해시 테이블 손님 번호로 칸 바로 배달 지도 7 그래프 · 길 가게와 집을 잇는 길 배지 = 실제 자료구조 · 번호 = 주문 하나가 지나가는 순서 · 배지 바탕 = 관계 모양(선형 · 계층 · 망 · 키 대응)

그림 1 · 주방장 민 씨는 주문을 받아 배달까지 가는 동안 물건마다 다른 정리법을 쓰고, 정리법마다 실제 자료구조 하나가 짝을 이룬다.

주문 받기레일에 온 순서대로
급한 주문종이 울리면 먼저
레시피 찾기메뉴판 분류를 따라
카드 넘기기고리의 다음 카드로
접시 꺼내기더미 맨 위부터
포장 맡기기손님 번호 칸에 바로
배달 길지도에서 이어진 길
들어온 주문 넷 — 들어온 순서 A → D · 숫자 1 = 가장 급함 A 냉면 급한 정도 4 B 국밥 급한 정도 2 C 죽 급한 정도 1 D 비빔밥 급한 정도 3 주문 레일 = 큐 먼저 꽂힌 주문이 먼저 나감 A B C D 가장 급한 C 는 세 번째로 나간다 급한 종 = 우선순위 큐 언제 왔든 가장 급한 주문이 먼저 C B D A 먼저 온 A 는 가장 늦게 나간다 왼쪽부터 나가는 순서 · 굵은 테두리 = 첫째로 나가는 주문 · 넣은 주문은 양쪽이 같다

그림 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 는 설명용 가정 값이다.

  1. 빈 캐시 = 해시 테이블(키 → 노드 위치) + 원형 이중 연결 리스트(머리 쪽 = 가장 오래 안 씀 · 꼬리 쪽 = 최근)와 지우지 않는 감시 노드 하나다(CPython OrderedDict).
  2. a · b · c 를 넣는다 — 표에 키 3개, 리스트는 감시 ⇄ a ⇄ b ⇄ c 다.
  3. a 를 읽는다 — 표에서 a 노드를 평균 상수 시간에 찾고(NIST DADS hash table), 이웃 두 링크를 이어 떼어 낸 뒤 꼬리에 링크 네 개로 붙인다(포인터 6개 · 직접 계산). 리스트는 b ⇄ c ⇄ a 다(move_to_end · Python collections).
  4. d 를 넣는다 — 표의 키가 4개로 용량을 넘는다.
  5. 머리 쪽 첫 노드 b 를 떼어 내고 표에서도 지운다(popitem(last=False) · Python collections). 리스트는 c ⇄ a ⇄ d 로 키 3개가 남는다.
  6. 리스트만 썼다면 3단계의 a 찾기에 최대 n 개 노드를 훑고, 표만 썼다면 5단계의 «가장 오래된 키»를 알려고 전부 훑는다. 둘을 묶어 모든 연산이 dict 와 같은 차수가 된다(CPython OrderedDict).
단계 해시 테이블 키 이중 연결 리스트(머리 = 가장 오래 안 씀 → 꼬리 = 최근) 2 a · b · c 넣기 a b c → 감시 a b c 3 a 읽기 a b c → 감시 b c a a 를 떼어 꼬리로 · 포인터 6개만 바꿈 5 d 넣고 b 내보냄 c a d → 감시 c a d b 머리 쪽 첫 노드 b 를 리스트와 표에서 지움 · 키 3개 유지 굵은 테두리 = 이 단계에 옮기거나 넣은 것 · 점선 = 내보낸 것 · 감시 노드 = 지우지 않는 머리 겸 꼬리

그림 4 · 읽힌 a 는 꼬리로 옮겨지고, 넘친 때는 머리 쪽 b 가 나가며, 해시 테이블은 «어디 있나»를, 연결 리스트는 «얼마나 오래됐나»를 맡는다.

끝에 넣기 · 빼기 키로 찾기 최소 꺼내기 범위 찾기(a ~ b) 스택 · 큐 O(1) O(n) O(n) O(n) 연결 리스트 O(1) * O(n) O(n) O(n) 트리(균형 탐색) O(log n) O(log n) O(log n) O(log n + k) 힙 · 우선순위 큐 O(log n) O(n) O(log n) O(n) 해시 테이블 평균 O(1) 평균 O(1) O(n) O(n) 상수 — 크기와 무관 로그 — n 이 2배면 한 단계 더 선형 — n 에 비례해 훑음 * 노드 위치를 이미 알 때 · k = 범위 안 항목 수 · 힙의 최소 «보기»는 heap[0] 이라 O(1)

그림 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시험 대비

출제 정보 정보관리(132회, 131회, 126회, 125회, 124회, 123회, 96회, 90회, 89회)문제 원문 — 큐넷 자료실 「기출문제(기술사)」 www.q-net.or.kr

시험에서는 자료구조의 분류(선형 · 비선형)와 각 구조의 특징 · 연산을 묻는 정의 · 특징형, 또는 스택 · 큐 · 힙에 값을 넣고 빼는 과정을 묻는 동작 · 절차 설명형으로 나올 수 있다. 어느 쪽이든 «관계 모양 → 지키는 규칙 → 싼 연산 · 비싼 연산» 순서를 먼저 세우고 묻는 구조를 그 위치에 놓는다.

답안 목차
  1. 개요 — 정의(값 + 연산의 약속 · NIST DADS abstract data type) · 추상 자료형과 구현의 분리(1974)
  2. 분류 — 그림 3 하위 토픽 지도(선형 · 계층 · 망 · 키 대응) + 하위 토픽 표(규칙 · 바탕 부품)
  3. 연산 비용 — 그림 5 구조 × 연산 표(상수 · 로그 · 선형)
  4. 동작 예 — 그림 4 LRU 캐시(해시 테이블 + 이중 연결 리스트 · 포인터 6개)
  5. 선택 기준 — 가장 자주 하는 연산 · 순서 필요 여부 · 범위 질의 여부
  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참고 문헌

  1. 먼저 볼 문헌
  2. ★ Dictionary of Algorithms and Data Structures - abstract data type (Paul E. Black ed.) — 자료구조를 구현과 떼어 «값 + 연산의 약속»으로 정의하는 공공 정의를 볼 때
    NIST · 2005-02 · xlinux.nist.gov/dads/HTML/abstractDataType.html · 확인 2026-11-14
  3. ★ Dictionary of Algorithms and Data Structures - linked list — 연결 리스트가 큐 · 스택 · 해시 버킷의 부품이 되는 관계를 볼 때
    NIST · 2022-01 · xlinux.nist.gov/dads/HTML/linkedList.html · 확인 2026-11-14
  4. ★ collections - Container datatypes (Python 3.15 documentation) — deque 와 list 의 앞쪽 연산 비용 · OrderedDict 의 move_to_end · popitem 을 볼 때
    Python Software Foundation · 2026-11 · docs.python.org/3/library/collections.html · 확인 2026-11-14
  5. ★ heapq - Heap queue algorithm (Python 3.15 documentation) — 배열에 담은 힙의 불변식(heap[k] <= heap[2*k+1])을 볼 때
    Python Software Foundation · 2026-11 · docs.python.org/3/library/heapq.html · 확인 2026-11-14
  6. 본문 근거
  7. Dictionary of Algorithms and Data Structures - stack — NIST · 2019-10 · xlinux.nist.gov/dads/HTML/stack.html · 확인 2026-11-14
  8. Dictionary of Algorithms and Data Structures - tree — NIST · 2017-12 · xlinux.nist.gov/dads/HTML/tree.html · 확인 2026-11-14
  9. Dictionary of Algorithms and Data Structures - heap — NIST · 2023-04 · xlinux.nist.gov/dads/HTML/heap.html · 확인 2026-11-14
  10. Dictionary of Algorithms and Data Structures - priority queue — NIST · 2021-11 · xlinux.nist.gov/dads/HTML/priorityque.html · 확인 2026-11-14
  11. Dictionary of Algorithms and Data Structures - graph — NIST · 2022-07 · xlinux.nist.gov/dads/HTML/graph.html · 확인 2026-11-14
  12. Dictionary of Algorithms and Data Structures - hash table — NIST · 2022-04 · xlinux.nist.gov/dads/HTML/hashtab.html · 확인 2026-11-14
  13. 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
  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
  15. 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
  16. 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
  17. 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