알면 유용한 자료구조들

들어가며#

프로그래밍 언어를 여러 개 배우다 보면 아래와 같은 생각을 해보셨을거에요.
"파이썬에서는 list, 자바에서는 ArrayList, C++의 vector 이렇게 문법이 다른데 자료구조 공부를 굳이 해야할까?"

그러나, 파이썬의 dict와 자바의 HashMap 등 모두 문법은 언어마다 제각각이지만, 그 바탕이 되는 자료구조는 거의 공통입니다.

자료구조란, 데이터를 어떤 모양으로 담아둘 것인가에 대한 약속입니다.
같은 데이터라도 어떻게 담느냐에 따라 찾는 속도, 넣고 빼는 속도가 크게 달라집니다. 그래서 자료구조를 한 번 제대로 이해해 두면 어떤 언어를 쓰든 "아, 이건 그거구나" 하고 금방 적응할 수 있습니다.

이 글에서는 거의 모든 언어에서 공통으로 쓰이는 자료구조와 이런 자료구조들을 이용한 알고리즘을 정리하였습니다. 예시 코드는 가장 읽기 쉽고 코테에서도 널리 쓰이는 파이썬으로 작성하였습니다.

시간 복잡도란?#

글 중간중간 나오는 O(1), O(N) 같은 표기는 시간 복잡도입니다.
시가 복잡도는 데이터가 N개일 때 작업에 걸리는 시간이 어떻게 늘어나는지를 나타냅니다.\

주요 시간 복잡도#

• O(1) (상수 시간, Constant): 입력 크기(N)와 상관없이 일정한 시간이 걸립니다.
• O(log N) (로그 시간, Logarithmic): 입력 크기가 커질 때 연산 횟수가 로그만큼 느리게 증가합니다.
• O(N) (선형 시간, Linear): 입력 크기에 비례하여 실행 시간이 늘어납니다.
• O(N²) (이차 시간, Quadratic): 입력 크기의 제곱에 비례하며, 주로 이중 반복문에서 발생합니다.
• O(2^N) (지수 시간, Exponential): 입력이 증가할수록 연산량이 기하급수적으로 증가합니다.

자료구조#

1. 배열 (Array)#

같은 타입의 데이터를 메모리에 빈틈없이 연속으로 저장합니다. 사물함이 일렬로 쭉 붙어 있고 각각에 번호가 매겨져 있다고 생각하시면 됩니다.

연속으로 붙어 있다는 점을 이용하면, 첫 번째 칸의 위치만 알면 5번째 칸이 어디 있는지 계산 한 번으로 바로 알 수 있습니다. 그래서 인덱스로 접근하는 속도가 O(1)로 매우 빠릅니다. 대신 처음 만들 때 크기가 정해지면 바꿀 수 없다는 단점이 있습니다.

C에서 int arr[4];처럼 쓰는 것이 바로 배열입니다. 파이썬에서는 보통 리스트를 쓰기 때문에 순수한 배열을 쓸 일이 많지 않지만, array 모듈을 사용하면 타입이 고정된 배열을 만들 수 있습니다.

from array import array
 
# 'i'는 정수(int)만 담겠다는 뜻입니다
scores = array('i', [90, 85, 77, 100])

print(scores[2]) # 77
scores[2] = 80
print(scores) # array('i', [90, 85, 80, 100])
 
# 타입이 고정되어 있어서 문자열은 넣을 수 없습니다
# scores[0] = "A"  # TypeError 발생

2. 동적 배열 (Dynamic Array, List)#

배열의 크기 고정 문제를 해결한 것이 동적 배열입니다. 공간이 부족해지면 더 큰 공간을 새로 잡고 기존 데이터를 통째로 옮겨서 크기를 늘립니다.

매번 옮기면 느리지 않을까 싶지만, 보통 한 번 늘릴 때 크기를 두 배 가까이 넉넉하게 잡기 때문에 옮기는 일은 가끔만 일어납니다. (관련 더모먼트 기술블로그)
그래서 끝에 추가하는 작업은 평균적으로 O(1)입니다. 다만 중간에 넣거나 빼면 뒤에 있는 원소들을 전부 한 칸씩 밀거나 당겨야 해서 O(n)이 걸립니다.

파이썬의 list가 바로 동적 배열입니다. 실무에서 가장 많이 쓰는 자료구조라고 해도 될 정도입니다.

fruits = ["사과", "바나나"]
 
fruits.append("딸기") # 끝에 추가: 빠릅니다
fruits.insert(0, "포도") # 맨 앞에 추가: 뒤 원소를 다 밀어야 해서 느립니다
 
print(fruits) # ['포도', '사과', '바나나', '딸기']
print(fruits[1]) # 사과
 
last = fruits.pop() # 끝에서 꺼내기
print(last) # 딸기
print(len(fruits)) # 3

3. 문자열 (String)#

문자열은 너무 익숙해서 자료구조라는 생각이 잘 들지 않지만, 문자들의 배열입니다.
그래서 앞에서 본 배열처럼 인덱스로 접근하고, 잘라내고(슬라이싱), 반복문으로 한 글자씩 순회할 수 있습니다.

C에서는 문자열이 말 그대로 char 배열이고, 끝에 \0을 붙여서 끝을 표시합니다. 파이썬을 비롯한 대부분의 현대 언어는 문자열을 별도의 타입으로 제공하며, 한 번 만든 문자열은 수정할 수 없습니다(불변, immutable). 문자열을 바꾸는 모든 작업은 사실 새 문자열을 만들어 돌려주는 것입니다.

4. 튜플과 구조체 (Tuple, Struct)#

지금까지는 주로 같은 종류의 데이터 여러 개를 담는 방법을 살펴보았습니다.
튜플과 구조체는 조금 다르게, 서로 다른 종류의 데이터를 하나로 묶어서 하나의 덩어리로 다루는 용도입니다.
예를 들어 "이름(문자열), 나이(숫자), 이메일(문자열)"을 묶어 한 명의 사용자로 표현하는 식입니다.

C에서는 struct, 자바에서는 클래스나 record가 이 역할을 합니다.

5. 해시 맵 (Hash Map, Dictionary)#

해시 맵은 키(key)와 값(value)을 한 쌍으로 저장하는 구조입니다.
사전에서 단어(키)를 찾으면 뜻(값)이 나오는 것처럼, 키만 알면 값을 바로 꺼낼 수 있습니다.

키를 해시 함수에 넣으면 숫자가 나오고, 그 숫자를 저장 위치로 사용합니다. 그래서 데이터가 백만 개가 있어도 처음부터 뒤질 필요 없이 계산 한 번으로 위치를 알아낼 수 있습니다. 조회, 삽입, 삭제 모두 평균 O(1)입니다.

실무에서 리스트와 함께 가장 많이 쓰는 자료구조입니다. "이름으로 사용자 정보 찾기", "단어별 등장 횟수 세기"처럼 무언가를 이름표로 찾아야 할 때는 거의 항상 해시 맵을 사용합니다. 파이썬에서는 dict가 여기에 해당합니다.

ages = {"철수": 25, "영희": 30}
 
ages["민수"] = 28 # 추가
ages["철수"] = 26 # 수정
print(ages["영희"]) # 30
 
print("민수" in ages) # True (키가 있는지 확인)
 
# 없는 키를 ages["지민"]처럼 꺼내면 KeyError가 발생합니다
# get()을 사용하면 기본값을 돌려받을 수 있습니다
print(ages.get("지민", 0))  # 0
 
for name, age in ages.items():
    print(name, age)
# 철수 26
# 영희 30
# 민수 28

6. 집합 (Set)#

집합은 중복을 허용하지 않는 값들의 모음입니다.
내부적으로는 바로 앞에서 본 해시 맵에서 값 없이 키만 저장하는 구조라고 생각하시면 됩니다. 그래서 "이 값이 들어 있는가?"를 확인하는 속도가 평균 O(1)로 매우 빠릅니다.

리스트에서 x in my_list를 하면 처음부터 끝까지 하나씩 비교하느라 O(N)이 걸립니다. 반면 집합에서는 즉시 확인할 수 있습니다. 그래서 포함 여부를 자주 확인해야 하거나, 중복을 없애야 할 때 집합을 사용합니다.

한 가지 주의할 점은 집합에는 순서가 없다는 것입니다. 넣은 순서대로 나온다는 보장이 없으므로, 순서가 중요하다면 정렬해서 사용해야 합니다.

numbers = [3, 1, 3, 2, 1, 3]
unique = set(numbers)
print(unique) # {1, 2, 3}

7. 스택 (Stack)#

스택은 나중에 넣은 것을 먼저 꺼내는 구조입니다.
이를 LIFO(Last In, First Out)라고 부릅니다.

스택은 저희 주변에서도 자주 쓰입니다. 에디터의 "실행 취소(Ctrl+Z)"는 방금 한 작업부터 되돌리는 스택이고, 브라우저의 뒤로 가기도 스택입니다.

stack = []
 
stack.append("A")
stack.append("B")
stack.append("C")
 
print(stack.pop()) # C (마지막에 넣은 것이 먼저 나옵니다)
print(stack.pop()) # B
print(stack[-1]) # A (꺼내지 않고 맨 위만 확인)

8. 큐 (Queue)#

큐는 스택의 반대로, 먼저 넣은 것을 먼저 꺼내는 구조입니다.
FIFO(First In, First Out)라고 부릅니다.

프린터 인쇄 대기열, 서버에 들어온 요청 처리, 그래프 탐색의 BFS(너비 우선 탐색) 등 순서대로 처리해야 하는 곳이라면 어디든 큐가 쓰입니다.

from collections import deque
 
queue = deque()
 
queue.append("손님1")
queue.append("손님2")
queue.append("손님3")
 
print(queue.popleft()) # 손님1  (먼저 온 사람이 먼저 나갑니다)
print(queue.popleft()) # 손님2
print(len(queue)) # 1

9. 덱 (Deque)#

덱은 Double-Ended Queue의 줄임말로, 양쪽 끝에서 모두 넣고 뺄 수 있는 큐입니다.
스택처럼도, 큐처럼도 쓸 수 있는 만능 도구라고 보시면 됩니다. 양쪽 끝의 작업이 모두 O(1)입니다.

from collections import deque
 
dq = deque([2, 3])
 
dq.appendleft(1) # 왼쪽에 추가
dq.append(4) # 오른쪽에 추가
print(dq) # deque([1, 2, 3, 4])
 
dq.popleft() # 왼쪽에서 꺼내기
dq.pop() # 오른쪽에서 꺼내기
print(dq) # deque([2, 3])
 
# 최근 본 상품 3개만 기억하기
recent = deque(maxlen=3)
for item in ["노트북", "마우스", "키보드", "모니터"]:
    recent.append(item)
 
print(recent) # deque(['마우스', '키보드', '모니터'], maxlen=3)

10. 연결 리스트 (Linked List)#

연결 리스트는 데이터를 연속으로 붙여두지 않고, 각 데이터(노드)가 다음 노드의 위치를 들고 있는 방식으로 줄줄이 이어 붙입니다.
보물찾기 쪽지처럼 '다음 쪽지는 ~에 있음'을 따라가는 구조입니다.

이렇게 하면 중간에 새 노드를 끼워 넣을 때 앞뒤 연결만 바꿔주면 되므로, 다른 원소를 밀 필요가 없습니다. 대신 n번째 원소를 찾으려면 처음부터 하나씩 따라가야 해서 접근이 O(n)으로 느립니다.

실무에서 연결 리스트를 직접 쓸 일은 많지 않습니다. 요즘 컴퓨터는 연속된 메모리를 읽는 데 최적화되어 있어서 대부분의 경우 동적 배열이 더 빠르기 때문입니다.
하지만 포인터 개념을 이해하는 데 좋고, 바로 다음에 나오는 트리나 그래프 같은 더 복잡한 구조의 기초가 되기 때문에 꼭 알아둘 필요가 있습니다. 파이썬에는 기본으로 제공되지 않으니 직접 만들어 보겠습니다.

11. 트리 (Tree)#

지금까지 살펴본 자료구조들은 대부분 데이터가 한 줄로 늘어선 선형 구조였습니다. 트리는 여기서 벗어나 부모와 자식 관계로 뻗어 나가는 계층 구조입니다.
컴퓨터의 폴더 구조, 회사 조직 모두 트리입니다. 연결 리스트의 노드가 다음 노드 하나를 가리켰다면, 트리의 노드는 "자식 노드" 여러 개를 가리킨다고 보시면 됩니다.

맨 꼭대기 노드를 루트(root), 자식이 없는 끝 노드를 리프(leaf)라고 부릅니다.

이진 탐색 트리에서 트리가 한쪽으로 치우치지 않고 균형이 잘 잡혀 있다면 탐색은 O(log n)입니다.

12. 힙 (Heap)과 우선순위 큐 (Priority Queue)#

큐는 먼저 온 순서대로 처리하지만, 순서보다 중요도가 우선일 때가 많습니다.
예를 들어 응급실에서는 먼저 온 환자보다 위급한 환자를 먼저 치료합니다. 이렇게 우선순위가 높은 것부터 꺼내는 큐를 우선순위 큐라고 하고, 이를 효율적으로 구현하는 자료구조가 힙입니다.

힙은 트리의 일종으로, 부모가 항상 자식보다 작다(최소 힙 기준)는 규칙만 지킵니다. 이진 탐색 트리처럼 전체가 정렬되어 있지는 않지만 맨 꼭대기에는 항상 가장 작은 값이 있습니다. 그래서 최솟값 확인은 O(1), 꺼내거나 넣는 것은 O(log n)입니다.

주로 최단 경로를 찾는 다익스트라 알고리즘 등에 쓰입니다.

import heapq
 
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 8)
heapq.heappush(heap, 3)
 
print(heap[0]) # 1  (가장 작은 값은 항상 맨 앞)
print(heapq.heappop(heap)) # 1
print(heapq.heappop(heap)) # 3

heapq는 최소 힙만 지원합니다. 큰 값부터 꺼내고 싶다면 값에 마이너스를 붙여서 넣는 꼼수?를 사용합니다.

import heapq
 
max_heap = []
for n in [5, 1, 8, 3]:
    heapq.heappush(max_heap, -n)
 
print(-heapq.heappop(max_heap)) # 8  (가장 큰 값)

14. 그래프 (Graph)#

그래프는 노드(정점)와 그 사이를 잇는 간선으로 이루어진 구조입니다.
트리도 사실 그래프의 한 종류인데, 그래프는 트리와 달리 부모-자식 같은 위계가 없고 연결에 제약도 없습니다. 서로가 서로를 가리킬 수도 있고, 빙글빙글 도는 순환이 생길 수도 있습니다.

인스타 팔로워/팔로잉 관계, 내비게이션의 도로망처럼 "무엇과 무엇이 연결되어 있다"를 표현해야 하는 모든 곳에 그래프가 있습니다.

백엔드에서는 어디에 쓰일까?#

백엔드에서 앞서 설명한 자료구조들이 쓰이는 예시를 간결하게 설명하겠습니다.

캐시 (해시 맵 + 연결리스트)#

자주 조회하는 데이터를 매번 데이터베이스에서 읽으면 느립니다.
그래서 메모리에 캐시로 저장해 두고 바로 꺼내 씁니다. 캐시는 키로 값을 평균 O(1)에 찾는 해시 맵 구조이며, Redis와 Memcached가 대표적입니다.

캐시가 가득 차면 가장 오래 사용하지 않은 데이터부터 지우는 LRU 방식을 주로 씁니다. 해시 맵으로 값을 찾고, 연결 리스트로 사용 순서를 관리합니다.

이메일 발송 (큐)#

이메일 발송처럼 오래 걸리는 작업은 바로 처리하지 않고 큐에 넣은 뒤 사용자에게 즉시 응답합니다.
이후 워커가 큐에서 먼저 들어온 작업부터 하나씩 처리합니다(FIFO).

요청이 몰려도 작업이 큐에 쌓일 뿐 서버가 멈추지 않고, 워커만 늘리면 처리 속도를 높일 수 있습니다. Kafka, RabbitMQ, Celery가 이 역할을 합니다.

데이터베이스 인덱스 (B+ 트리)#

수백만 건의 데이터에서도 WHERE id = 999999 조회가 빠른 이유는 인덱스 덕분이며, 인덱스는 트리로 만들어집니다. MySQL(InnoDB)은 B+트리를 사용합니다.

B+트리는 노드 하나가 자식을 수백 개씩 가져서 수백만 건이어도 높이가 3~4층에 불과합니다. 또 맨 아래 노드들이 옆으로 연결되어 있어 범위 검색(BETWEEN)도 빠릅니다.

프론트엔드에서는 어디에 쓰일까?#

프론트엔드에서 앞서 설명한 자료구조들이 쓰이는 예시를 간결하게 설명하겠습니다.

실행 취소 / 다시 실행 (스택)#

실행 취소(Ctrl+Z)는 가장 최근 작업부터 되돌리므로 스택(LIFO)을 사용합니다.
그리고 스택 두 개를 사용하는데, 작업할 때마다 이전 상태를 실행 취소 스택에 쌓고, 되돌린 상태는 다시 실행 스택으로 옮깁니다.
새 작업을 하면 다시 실행 스택은 비웁니다.

이벤트 루프 (큐)#

자바스크립트는 한 번에 한 가지 일만 하는 싱글 스레드 언어입니다. 그래서 setTimeout이나 클릭 이벤트의 콜백은 태스크 큐에, Promise의 콜백은 마이크로태스크 큐에 줄을 세워 두고 순서대로 실행합니다.

규칙은 콜 스택이 비면 마이크로태스크 큐를 전부 비운 뒤, 태스크 큐에서 하나를 꺼내는 것입니다. 그래서 아래 코드에서 setTimeout이 0초인데도 Promise보다 늦게 실행됩니다.

DOM과 Virtual DOM (트리)#

브라우저는 HTML을 DOM 트리로 바꿔서 화면을 그립니다. 하지만 DOM을 직접 수정하는 작업은 비용이 큽니다.

그래서 React는 메모리에 **Virtual DOM(가상 트리)**을 두고, 상태가 바뀌면 이전 트리와 비교해 달라진 부분만 실제 DOM에 반영합니다.
비교는 부모에서 자식으로 내려가는 재귀로 이루어집니다.

마치며#

14가지라고 하니 많아 보이지만, 처음부터 전부 외울 필요는 없습니다.
실제로 코드를 짜다 보면 간단한 자료구조만으로 대부분의 문제가 해결됩니다.
특히 리스트, 딕셔너리, 집합 이 세 가지는 매일같이 쓰게 됩니다. 여기에 힙(heapq) 정도를 더하면 웬만한 알고리즘 문제도 충분히 풀 수 있습니다.

만약 이 글을 바탕으로 공부하실 때는 이 글의 순서를 그대로 따라가시는 것을 추천합니다. 뒤 단계의 자료구조는 앞 단계의 개념을 바탕으로 만들어져 있어서, 순서대로 익히면 훨씬 쉽게 이해가 가능합니다.

여기서 중요한 것은 이름을 외우는 것이 아니라 "이 상황에서는 어떤 모양으로 데이터를 담아야 빠를까?"를 떠올리는 습관입니다.
값을 자주 찾아야 하면 해시 맵, 순서대로 처리해야 하면 큐, 가장 급한 것부터 처리해야 하면 힙. 이런 감각이 생기면 새로운 언어를 배울 때도 문법만 익히면 바로 적응할 수 있습니다.
결국 언어는 달라도 자료구조는 똑같기 때문입니다.