**자료구조(Data Structure)**는 데이터를 효율적으로 저장하고 관리하는 방법입니다. 올바른 자료구조 선택은 프로그램의 성능을 크게 좌우합니다. 이 글에서는 핵심 자료구조들을 시각적으로 설명하겠습니다.
선형 자료구조 vs 비선형 자료구조
자료구조는 크게 두 가지로 분류됩니다.
| 분류 | 특징 | 예시 |
|---|---|---|
| 선형 (Linear) | 데이터가 순차적으로 연결 | 배열, 연결 리스트, 스택, 큐 |
| 비선형 (Non-linear) | 데이터가 계층적/망형 연결 | 트리, 그래프, 힙 |
배열 vs 연결 리스트
가장 기본적인 두 자료구조를 비교해 보겠습니다.
배열 (Array)
배열은 연속된 메모리 공간에 동일한 타입의 데이터를 저장합니다.
# Python 배열 (리스트)
arr = [10, 20, 30, 40, 50]
# 인덱스로 접근 - O(1)
print(arr[2]) # 30
# 끝에 추가 - O(1) amortized
arr.append(60)
# 중간에 삽입 - O(n)
arr.insert(2, 25) # [10, 20, 25, 30, 40, 50, 60]
# 삭제 - O(n)
arr.remove(25)
// JavaScript 배열
const arr = [10, 20, 30, 40, 50];
// 인덱스로 접근 - O(1)
console.log(arr[2]); // 30
// 끝에 추가/제거 - O(1)
arr.push(60);
arr.pop();
// 앞에 추가/제거 - O(n)
arr.unshift(5);
arr.shift();
연결 리스트 (Linked List)
연결 리스트는 노드와 포인터로 데이터를 연결합니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# 앞에 삽입 - O(1)
def prepend(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
# 끝에 삽입 - O(n), tail 포인터 있으면 O(1)
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
# 검색 - O(n)
def search(self, data):
current = self.head
while current:
if current.data == data:
return True
current = current.next
return False
# 삭제 - O(1) (노드 참조가 있는 경우)
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
# 사용 예제
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.prepend(5)
연결 리스트의 변형으로 **이중 연결 리스트(Doubly Linked List)**와 **원형 연결 리스트(Circular Linked List)**가 있습니다. 이중 연결 리스트는 양방향 탐색이 가능합니다.
스택과 큐
스택과 큐는 데이터의 삽입/삭제 순서가 정해진 자료구조입니다.
스택 (Stack)
스택은 후입선출(LIFO) 구조입니다. 접시 쌓기를 생각하면 됩니다.
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self.items[-1]
def size(self):
return len(self.items)
# 사용 예제
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop()) # 30
print(stack.peek()) # 20
스택 활용 예제: 괄호 검사
def is_valid_parentheses(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping.values():
stack.append(char)
elif char in mapping.keys():
if not stack or stack.pop() != mapping[char]:
return False
return len(stack) == 0
# 테스트
print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("([)]")) # False
print(is_valid_parentheses("{[()]}")) # True
큐 (Queue)
큐는 선입선출(FIFO) 구조입니다. 줄 서기를 생각하면 됩니다.
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def is_empty(self):
return len(self.items) == 0
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.items.popleft()
def front(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self.items[0]
def size(self):
return len(self.items)
# 사용 예제
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.dequeue()) # 10
print(queue.front()) # 20
Python에서 리스트로 큐를 구현하면
pop(0)이 O(n)입니다. deque를 사용하면 양쪽 끝 연산이 모두 O(1)입니다.우선순위 큐 (Priority Queue)
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
def push(self, item, priority):
heapq.heappush(self.heap, (priority, item))
def pop(self):
if not self.heap:
raise IndexError("Priority queue is empty")
return heapq.heappop(self.heap)[1]
def peek(self):
if not self.heap:
raise IndexError("Priority queue is empty")
return self.heap[0][1]
# 사용 예제 - 작은 우선순위가 먼저 나옴
pq = PriorityQueue()
pq.push("Task C", 3)
pq.push("Task A", 1)
pq.push("Task B", 2)
print(pq.pop()) # Task A (priority 1)
print(pq.pop()) # Task B (priority 2)
해시 테이블 (Hash Table)
해시 테이블은 키-값 쌍을 저장하며, 평균 O(1) 시간에 검색이 가능합니다.
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
pair[1] = value
return
self.table[index].append([key, value])
def get(self, key):
index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
return pair[1]
raise KeyError(key)
def remove(self, key):
index = self._hash(key)
for i, pair in enumerate(self.table[index]):
if pair[0] == key:
del self.table[index][i]
return
raise KeyError(key)
# Python 딕셔너리가 해시 테이블 구현체
person = {
"name": "Kim",
"age": 25,
"city": "Seoul"
}
# 접근 - O(1) 평균
print(person["name"]) # Kim
person["email"] = "kim@example.com" # 추가
del person["age"] # 삭제
| 연산 | 평균 시간 | 최악 시간 |
|---|---|---|
| 검색 | O(1) | O(n) |
| 삽입 | O(1) | O(n) |
| 삭제 | O(1) | O(n) |
해시 충돌이 많이 발생하면 성능이 O(n)으로 저하됩니다. 좋은 해시 함수와 적절한 테이블 크기가 중요합니다.
트리와 그래프
비선형 자료구조인 트리와 그래프는 계층적/망형 관계를 표현합니다.
이진 탐색 트리 (BST)
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
self._insert_recursive(self.root, val)
def _insert_recursive(self, node, val):
if val < node.val:
if node.left:
self._insert_recursive(node.left, val)
else:
node.left = TreeNode(val)
else:
if node.right:
self._insert_recursive(node.right, val)
else:
node.right = TreeNode(val)
def search(self, val):
return self._search_recursive(self.root, val)
def _search_recursive(self, node, val):
if not node:
return False
if val == node.val:
return True
if val < node.val:
return self._search_recursive(node.left, val)
return self._search_recursive(node.right, val)
# 중위 순회 - 정렬된 순서로 출력
def inorder(self, node, result=None):
if result is None:
result = []
if node:
self.inorder(node.left, result)
result.append(node.val)
self.inorder(node.right, result)
return result
# 사용 예제
bst = BST()
for val in [50, 30, 70, 20, 40, 60, 80]:
bst.insert(val)
print(bst.search(40)) # True
print(bst.inorder(bst.root)) # [20, 30, 40, 50, 60, 70, 80]
그래프 (Graph)
from collections import defaultdict, deque
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def add_edge(self, u, v):
self.graph[u].append(v)
if not self.directed:
self.graph[v].append(u)
# 너비 우선 탐색 (BFS)
def bfs(self, start):
visited = set()
queue = deque([start])
result = []
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
result.append(vertex)
queue.extend(
neighbor for neighbor in self.graph[vertex]
if neighbor not in visited
)
return result
# 깊이 우선 탐색 (DFS)
def dfs(self, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in self.graph[start]:
if neighbor not in visited:
result.extend(self.dfs(neighbor, visited))
return result
# 사용 예제
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.add_edge('D', 'E')
print("BFS:", g.bfs('A')) # ['A', 'B', 'C', 'D', 'E']
print("DFS:", g.dfs('A')) # ['A', 'B', 'D', 'C', 'E']
자료구조 선택 가이드
| 상황 | 추천 자료구조 |
|---|---|
| 인덱스로 빠른 접근 필요 | 배열 |
| 잦은 삽입/삭제 | 연결 리스트 |
| 후입선출 처리 | 스택 |
| 선입선출 처리 | 큐 |
| 우선순위 기반 처리 | 힙 / 우선순위 큐 |
| 키-값 저장, 빠른 검색 | 해시 테이블 |
| 정렬된 데이터 유지 | BST / AVL / Red-Black Tree |
| 계층 구조 표현 | 트리 |
| 관계/네트워크 표현 | 그래프 |
마무리
자료구조는 효율적인 프로그래밍의 기초입니다. 각 자료구조의 특성과 시간 복잡도를 이해하면 상황에 맞는 최적의 선택을 할 수 있습니다.
다음 단계로 추천하는 학습 경로:
- 정렬 알고리즘: 버블, 선택, 삽입, 병합, 퀵 정렬
- 탐색 알고리즘: 이진 탐색, BFS, DFS
- 동적 프로그래밍: 메모이제이션과 타뷸레이션
- 그래프 알고리즘: 다익스트라, 벨만-포드, 프림, 크루스칼