자료구조 (Data Structures)¶
데이터를 효율적으로 저장하고 접근하기 위한 구조. LLM/VLM에서는 토큰 시퀀스 처리, KV Cache, 토크나이저 구현 등에 직접 활용됨.
왜 자료구조를 알아야 하는가¶
- 효율성: 같은 문제도 자료구조에 따라 성능이 천차만별
- 트레이드오프 이해: 시간 vs 공간, 읽기 vs 쓰기
- 추상화 능력: 문제를 적절한 자료구조로 모델링하는 능력
- 면접: FAANG부터 국내 기업까지 필수 질문
기본 자료구조¶
배열 (Array)¶
연속된 메모리 공간에 동일 타입 데이터를 저장하는 구조.
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| 접근 | O(1) | 인덱스로 직접 접근 (base + index * size) |
| 탐색 | O(n) | 순차 탐색 필요 |
| 삽입 | O(n) | 요소 이동 필요 |
| 삭제 | O(n) | 요소 이동 필요 |
| 끝에 추가 | O(1) amortized | 동적 배열의 경우 |
왜 O(1) 접근이 가능한가?
메모리 주소 계산:
address = base_address + (index * element_size)
예: int 배열 (4바이트), base=1000
arr[3]의 주소 = 1000 + (3 * 4) = 1012
동적 배열 (Dynamic Array)
Python의 list, Java의 ArrayList는 동적 배열.
# Python 리스트의 실제 동작
arr = []
arr.append(1) # capacity 4로 시작
arr.append(2)
arr.append(3)
arr.append(4)
arr.append(5) # capacity 초과 -> 2배로 확장 (8)
# 확장 시 O(n) 복사 발생
# 하지만 amortized O(1): n번 삽입에 총 O(n) 시간
LLM 관련 예시:
# 토큰 ID 시퀀스
token_ids = [101, 2054, 2003, 1037, 4937, 102] # [CLS] what is a model [SEP]
# NumPy 배열 (텐서 연산에 최적화)
import numpy as np
embeddings = np.array([[0.1, 0.2, 0.3], [0.4, 0.5, 0.6]])
# 연속 메모리 -> CPU 캐시 효율적
# 벡터화 연산 가능
실무 활용: - 토큰 ID 시퀀스 저장 - 임베딩 행렬 (2D 배열) - 어텐션 스코어 행렬 - 배치 데이터 구성
연결 리스트 (Linked List)¶
각 노드가 데이터와 다음 노드 포인터를 가지는 구조.
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| 접근 | O(n) | 순차 탐색 필요 |
| 탐색 | O(n) | 순차 탐색 필요 |
| 삽입 | O(1) | 포인터만 변경 (위치를 알 경우) |
| 삭제 | O(1) | 포인터만 변경 (위치를 알 경우) |
단일 연결 리스트:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def prepend(self, data):
"""앞에 추가: O(1)"""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def delete(self, data):
if not self.head:
return
if self.head.data == data:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.data == data:
current.next = current.next.next
return
current = current.next
이중 연결 리스트:
class DNode:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, data):
new_node = DNode(data)
if not self.tail:
self.head = self.tail = new_node
return
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
def remove(self, node):
"""노드 참조가 있으면 O(1) 삭제"""
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev
배열 vs 연결 리스트:
| 측면 | 배열 | 연결 리스트 |
|---|---|---|
| 메모리 | 연속, 캐시 효율적 | 분산, 오버헤드 (포인터) |
| 접근 | O(1) | O(n) |
| 중간 삽입/삭제 | O(n) | O(1) (위치 알면) |
| 크기 조절 | 복사 필요 | 유연 |
| 실무 사용 | 대부분의 경우 | LRU 캐시, 특수 상황 |
실무에서 연결 리스트를 쓰는 경우: - LRU 캐시 (해시맵 + 이중 연결 리스트) - 파일 시스템의 빈 블록 관리 - Undo/Redo 구현 - 다항식 표현
스택 (Stack)¶
LIFO(Last In First Out) 구조. 가장 최근에 넣은 것이 먼저 나온다.
| 연산 | 시간 복잡도 |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek/top | O(1) |
| isEmpty | O(1) |
# Python 리스트를 스택으로 사용
stack = []
stack.append(1) # push
stack.append(2)
top = stack.pop() # pop -> 2
# collections.deque (더 효율적, 스레드 안전)
from collections import deque
stack = deque()
stack.append(1)
stack.pop()
스택 활용 사례:
# 1. 괄호 매칭
def is_valid_parentheses(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in '([{':
stack.append(char)
elif char in ')]}':
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return len(stack) == 0
# 2. 후위 표기법 계산
def eval_postfix(tokens):
stack = []
for token in tokens:
if token.isdigit():
stack.append(int(token))
else:
b, a = stack.pop(), stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
elif token == '/': stack.append(a // b)
return stack[0]
# 3. DFS 구현 (비재귀)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
호출 스택 (Call Stack):
큐 (Queue)¶
FIFO(First In First Out) 구조. 먼저 넣은 것이 먼저 나온다.
| 연산 | 시간 복잡도 |
|---|---|
| enqueue | O(1) |
| dequeue | O(1) |
| front/peek | O(1) |
| isEmpty | O(1) |
from collections import deque
# 일반 큐
queue = deque()
queue.append(1) # enqueue (오른쪽에 추가)
queue.append(2)
first = queue.popleft() # dequeue (왼쪽에서 제거) -> 1
# 리스트로 구현하면 dequeue가 O(n)이 되므로 deque 사용 권장
원형 큐 (Circular Queue):
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.front = 0
self.rear = -1
self.size = 0
def enqueue(self, item):
if self.is_full():
raise Exception("Queue is full")
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = item
self.size += 1
def dequeue(self):
if self.is_empty():
raise Exception("Queue is empty")
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item
def is_full(self):
return self.size == self.capacity
def is_empty(self):
return self.size == 0
우선순위 큐 (Priority Queue):
힙으로 구현되며, 우선순위가 높은 요소가 먼저 나온다.
import heapq
# 최소 힙 (기본)
pq = []
heapq.heappush(pq, (1, 'low priority'))
heapq.heappush(pq, (3, 'high priority'))
heapq.heappush(pq, (2, 'medium priority'))
item = heapq.heappop(pq) # (1, 'low priority')
# 최대 힙 (값에 -1 곱하기)
max_pq = []
heapq.heappush(max_pq, (-3, 'high priority'))
heapq.heappush(max_pq, (-1, 'low priority'))
priority, data = heapq.heappop(max_pq)
print(-priority, data) # 3, 'high priority'
큐 활용 사례: - BFS (너비 우선 탐색) - 작업 스케줄링 - 이벤트 처리 - LLM 서빙 시스템의 요청 큐
고급 자료구조¶
해시 테이블 (Hash Table)¶
키-값 쌍을 저장하는 구조. 해시 함수를 통해 O(1) 평균 접근.
| 연산 | 평균 | 최악 |
|---|---|---|
| 검색 | O(1) | O(n) |
| 삽입 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |
해시 함수의 역할:
해시 충돌 해결:
# 1. 체이닝 (Chaining): 같은 인덱스에 연결 리스트
class HashTableChaining:
def __init__(self, size=10):
self.size = size
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
idx = self._hash(key)
for i, (k, v) in enumerate(self.buckets[idx]):
if k == key:
self.buckets[idx][i] = (key, value)
return
self.buckets[idx].append((key, value))
def get(self, key):
idx = self._hash(key)
for k, v in self.buckets[idx]:
if k == key:
return v
return None
# 2. 개방 주소법 (Open Addressing): 다른 빈 슬롯 찾기
# - 선형 탐사: 다음 슬롯
# - 이차 탐사: 1, 4, 9, ... 칸씩 이동
# - 이중 해싱: 두 번째 해시 함수로 이동 거리 결정
Load Factor와 리해싱:
Python dict의 동작:
# Python 3.7+: 삽입 순서 보장 (OrderedDict 불필요)
vocab = {
'hello': 1234,
'world': 5678,
'[UNK]': 0
}
# 토큰 -> ID 변환 (O(1))
def encode(text, vocab):
return [vocab.get(token, vocab['[UNK]']) for token in text.split()]
# dict comprehension
id_to_token = {v: k for k, v in vocab.items()}
실무 활용: - 어휘 사전 (Vocabulary) - 토큰-ID 매핑 - KV Cache 저장 - 메모이제이션 - 카운팅 (Counter)
힙 (Heap)¶
완전 이진 트리 기반의 자료구조. 부모가 자식보다 항상 크거나(최대 힙) 작음(최소 힙).
| 연산 | 시간 복잡도 |
|---|---|
| 삽입 | O(log n) |
| 최소/최대 삭제 | O(log n) |
| 최소/최대 조회 | O(1) |
| 힙 구성 (heapify) | O(n) |
배열로 힙 표현:
부모 인덱스: (i - 1) // 2
왼쪽 자식: 2 * i + 1
오른쪽 자식: 2 * i + 2
예: [1, 3, 2, 7, 6, 4, 5]
1(0)
/ \
3(1) 2(2)
/ \ / \
7(3) 6(4) 4(5) 5(6)
힙 구현:
class MinHeap:
def __init__(self):
self.heap = []
def push(self, val):
self.heap.append(val)
self._sift_up(len(self.heap) - 1)
def pop(self):
if not self.heap:
return None
if len(self.heap) == 1:
return self.heap.pop()
root = self.heap[0]
self.heap[0] = self.heap.pop()
self._sift_down(0)
return root
def _sift_up(self, idx):
parent = (idx - 1) // 2
while idx > 0 and self.heap[idx] < self.heap[parent]:
self.heap[idx], self.heap[parent] = self.heap[parent], self.heap[idx]
idx = parent
parent = (idx - 1) // 2
def _sift_down(self, idx):
n = len(self.heap)
while True:
smallest = idx
left = 2 * idx + 1
right = 2 * idx + 2
if left < n and self.heap[left] < self.heap[smallest]:
smallest = left
if right < n and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest == idx:
break
self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx]
idx = smallest
heapq 모듈 활용:
import heapq
# Top-K 문제: K번째로 큰/작은 요소
def find_kth_largest(nums, k):
# 최소 힙으로 k개 유지
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
return heap[0]
# 두 정렬된 리스트 병합
def merge_sorted_lists(lists):
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
result = []
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(lists[list_idx]):
next_val = lists[list_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
return result
LLM에서의 활용: - Top-k 토큰 선택 - Beam Search의 후보 관리 - 배치 스케줄링
트리 (Tree)¶
계층적 구조를 표현하는 비선형 자료구조.
용어: - 루트 (Root): 최상위 노드 - 리프 (Leaf): 자식이 없는 노드 - 깊이 (Depth): 루트로부터의 거리 - 높이 (Height): 가장 깊은 리프까지의 거리
이진 트리 (Binary Tree)¶
각 노드가 최대 2개의 자식을 가지는 트리.
트리 순회:
# 전위 순회 (Preorder): 루트 -> 왼쪽 -> 오른쪽
def preorder(node):
if node:
print(node.val)
preorder(node.left)
preorder(node.right)
# 중위 순회 (Inorder): 왼쪽 -> 루트 -> 오른쪽
# BST에서 정렬된 순서로 출력
def inorder(node):
if node:
inorder(node.left)
print(node.val)
inorder(node.right)
# 후위 순회 (Postorder): 왼쪽 -> 오른쪽 -> 루트
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.val)
# 레벨 순회 (Level-order): BFS
from collections import deque
def levelorder(root):
if not root:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
이진 탐색 트리 (BST)¶
왼쪽 서브트리의 모든 값 < 루트 < 오른쪽 서브트리의 모든 값
class BST:
def __init__(self):
self.root = None
def insert(self, val):
self.root = self._insert(self.root, val)
def _insert(self, node, val):
if not node:
return TreeNode(val)
if val < node.val:
node.left = self._insert(node.left, val)
else:
node.right = self._insert(node.right, val)
return node
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if not node or node.val == val:
return node
if val < node.val:
return self._search(node.left, val)
return self._search(node.right, val)
def delete(self, val):
self.root = self._delete(self.root, val)
def _delete(self, node, val):
if not node:
return None
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
# 삭제할 노드 찾음
if not node.left:
return node.right
if not node.right:
return node.left
# 두 자식 있음: 오른쪽 서브트리의 최소값으로 대체
min_node = self._find_min(node.right)
node.val = min_node.val
node.right = self._delete(node.right, min_node.val)
return node
def _find_min(self, node):
while node.left:
node = node.left
return node
BST의 문제점과 균형 트리:
편향된 BST (최악의 경우):
1
\
2
\
3
\
4
-> 모든 연산이 O(n)
해결: 균형 트리
- AVL 트리: 높이 차이 1 이하 유지
- Red-Black 트리: 색깔 규칙으로 균형 유지
- B-트리: 데이터베이스 인덱스에 사용
트라이 (Trie)¶
문자열 검색에 특화된 트리 구조. 접두사(Prefix) 검색에 효율적.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
self.token_id = None
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word, token_id=None):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
node.token_id = token_id
def search(self, word):
node = self._find_node(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find_node(prefix) is not None
def _find_node(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
def find_words_with_prefix(self, prefix):
"""접두사로 시작하는 모든 단어 찾기"""
node = self._find_node(prefix)
if not node:
return []
results = []
self._dfs(node, prefix, results)
return results
def _dfs(self, node, path, results):
if node.is_end:
results.append(path)
for char, child in node.children.items():
self._dfs(child, path + char, results)
LLM에서의 활용: - BPE 토크나이저의 어휘 저장 - 접두사 매칭 (자동 완성) - 제약 디코딩 (Constrained Decoding)
그래프 (Graph)¶
노드(정점)와 간선으로 구성된 비선형 자료구조.
표현 방식:
# 1. 인접 리스트 (Adjacency List) - 희소 그래프에 효율적
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 2. 인접 행렬 (Adjacency Matrix) - 밀집 그래프, 빠른 엣지 확인
# A B C D E F
# A [0, 1, 1, 0, 0, 0]
# B [1, 0, 0, 1, 1, 0]
# C [1, 0, 0, 0, 0, 1]
# ...
import numpy as np
adj_matrix = np.array([
[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 0]
])
그래프 탐색:
from collections import deque
# BFS (너비 우선 탐색)
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# DFS (깊이 우선 탐색) - 재귀
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
# DFS - 반복 (스택)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
return result
최단 경로 알고리즘:
# 다익스트라 (Dijkstra) - 음이 아닌 가중치
import heapq
def dijkstra(graph, start):
"""graph: {node: [(neighbor, weight), ...]}"""
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
dist, node = heapq.heappop(pq)
if dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return distances
LLM에서의 활용: - 지식 그래프 (Knowledge Graph) - 의존성 파싱 트리 - 계산 그래프 (Computational Graph)
LLM 특화 자료구조¶
KV Cache¶
Transformer 추론 시 Key-Value 쌍을 캐싱하여 중복 계산 방지.
class KVCache:
"""
Autoregressive 생성에서 이전 토큰의 K, V를 저장
새 토큰 생성 시 재계산 없이 캐시된 값 사용
"""
def __init__(self, max_seq_len, num_layers, num_heads, head_dim):
self.max_seq_len = max_seq_len
self.cache_k = {} # layer_idx -> tensor
self.cache_v = {}
self.num_heads = num_heads
self.head_dim = head_dim
def update(self, layer_idx, key, value, position):
"""새로운 토큰의 K, V 추가"""
batch_size = key.size(0)
if layer_idx not in self.cache_k:
# 초기화: (batch, max_seq, num_heads, head_dim)
self.cache_k[layer_idx] = torch.zeros(
batch_size, self.max_seq_len, self.num_heads, self.head_dim
)
self.cache_v[layer_idx] = torch.zeros(
batch_size, self.max_seq_len, self.num_heads, self.head_dim
)
# 새로운 K, V 저장
self.cache_k[layer_idx][:, position] = key
self.cache_v[layer_idx][:, position] = value
# 현재까지의 K, V 반환
return (
self.cache_k[layer_idx][:, :position+1],
self.cache_v[layer_idx][:, :position+1]
)
def get_seq_len(self, layer_idx):
if layer_idx not in self.cache_k:
return 0
return (self.cache_k[layer_idx].sum(dim=-1) != 0).sum(dim=-1).max().item()
메모리 계산:
KV Cache 메모리 = 2 * batch * layers * seq_len * num_heads * head_dim * precision
예: Llama-7B (batch=1, layers=32, seq=4096, heads=32, head_dim=128, FP16)
= 2 * 1 * 32 * 4096 * 32 * 128 * 2 bytes
= 2GB
토큰 버퍼¶
스트리밍 출력을 위한 토큰 관리.
class TokenBuffer:
"""
스트리밍 생성 시 토큰을 버퍼링하고
완전한 단어/문장 단위로 출력
"""
def __init__(self, tokenizer):
self.tokenizer = tokenizer
self.token_ids = []
self.text_offset = 0
def add(self, token_id):
self.token_ids.append(token_id)
def get_new_text(self):
"""새로 생성된 텍스트만 반환"""
full_text = self.tokenizer.decode(self.token_ids)
new_text = full_text[self.text_offset:]
self.text_offset = len(full_text)
return new_text
def flush(self):
"""모든 텍스트 반환 후 초기화"""
full_text = self.tokenizer.decode(self.token_ids)
self.token_ids = []
self.text_offset = 0
return full_text
시간/공간 복잡도 비교¶
| 자료구조 | 접근 | 검색 | 삽입 | 삭제 | 공간 |
|---|---|---|---|---|---|
| 배열 | O(1) | O(n) | O(n) | O(n) | O(n) |
| 연결 리스트 | O(n) | O(n) | O(1)* | O(1)* | O(n) |
| 스택/큐 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 해시 테이블 | - | O(1) avg | O(1) avg | O(1) avg | O(n) |
| BST (균형) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| 힙 | - | O(n) | O(log n) | O(log n) | O(n) |
| 트라이 | - | O(m) | O(m) | O(m) | O(n*m) |
*위치를 알고 있을 때
m: 문자열 길이, n: 요소 개수
핵심 개념¶
자주 나오는 질문¶
- 배열 vs 연결 리스트 차이점과 각각 언제 사용하는지?
- 배열: 랜덤 접근, 캐시 효율, 크기 고정
-
연결 리스트: 동적 크기, 중간 삽입/삭제 빈번
-
해시 충돌 해결 방법은?
- 체이닝: 연결 리스트로 저장
-
개방 주소법: 선형 탐사, 이차 탐사, 이중 해싱
-
스택 2개로 큐 구현하기
class QueueUsingStacks:
def __init__(self):
self.s1 = [] # push용
self.s2 = [] # pop용
def push(self, x):
self.s1.append(x)
def pop(self):
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
- 힙으로 Top-K 문제 풀기
- 최대 K개 -> 최소 힙 사용
-
최소 K개 -> 최대 힙 사용
-
트리 순회 (전위, 중위, 후위)의 특징
- 중위 순회 + BST = 정렬된 출력
-
후위 순회: 삭제할 때 유용 (자식 먼저 처리)
-
그래프 BFS vs DFS 언제 사용?
- BFS: 최단 경로, 레벨 순회
- DFS: 백트래킹, 사이클 탐지, 위상 정렬
실전 팁¶
1. 자료구조 선택 시 트레이드오프 고려
- "왜 이 자료구조를 선택했는지" 설명 필수
2. 시간/공간 복잡도는 반드시 분석
- 평균 vs 최악 구분
3. 엣지 케이스 고려
- 빈 입력, 단일 요소, 중복 값
4. 실무 연결
- "이 자료구조가 실제로 어디서 쓰이는지"