자료구조
복잡도 비교
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| Hash Table | — | O(1)* | O(1)* | O(1)* |
| BST | O(log n)* | O(log n)* | O(log n)* | O(log n)* |
| Heap | — | O(n) | O(log n) | O(log n) |
스택 & 큐
# 스택 (LIFO)
stack = []
stack.append(1)
stack.pop()
# 큐 (FIFO)
from collections import deque
queue = deque()
queue.append(1)
queue.popleft()
# 우선순위 큐 (최소 힙)
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappop(heap) # 1연결 리스트
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, val):
node = Node(val)
if not self.head:
self.head = node
return
cur = self.head
while cur.next:
cur = cur.next
cur.next = node
def reverse(self):
prev, cur = None, self.head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
self.head = prev이진 탐색 트리 (BST)
class BSTNode:
def __init__(self, val):
self.val = val
self.left = self.right = None
def insert(root, val):
if not root: return BSTNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
def search(root, val):
if not root or root.val == val: return root
if val < root.val: return search(root.left, val)
return search(root.right, val)
# 중위 순회 → 정렬된 순서
def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)힙 (Heap)
완전 이진 트리로 구현된 우선순위 큐.
부모 인덱스: (i-1) // 2
왼쪽 자식: 2*i + 1
오른쪽 자식: 2*i + 2
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):
self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
val = self.heap.pop()
self._sift_down(0)
return val
def _sift_up(self, i):
parent = (i - 1) // 2
if i > 0 and self.heap[i] < self.heap[parent]:
self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
self._sift_up(parent)
def _sift_down(self, i):
n = len(self.heap)
smallest = i
l, r = 2*i+1, 2*i+2
if l < n and self.heap[l] < self.heap[smallest]: smallest = l
if r < n and self.heap[r] < self.heap[smallest]: smallest = r
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
self._sift_down(smallest)트라이 (Trie)
문자열 검색에 특화된 트리. 자동완성, 사전 구현에 사용.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children: return False
node = node.children[ch]
return node.is_end
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children: return False
node = node.children[ch]
return True유니온-파인드 (Union-Find)
집합의 합치기/소속 확인. 크루스칼, 사이클 감지에 사용.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 경로 압축
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True세그먼트 트리
구간 합/최솟값 쿼리를 O(log n)에 처리.
class SegTree:
def __init__(self, arr):
n = len(arr)
self.tree = [0] * (4 * n)
self.build(arr, 1, 0, n-1)
def build(self, arr, node, start, end):
if start == end:
self.tree[node] = arr[start]
else:
mid = (start + end) // 2
self.build(arr, 2*node, start, mid)
self.build(arr, 2*node+1, mid+1, end)
self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
def query(self, node, start, end, l, r):
if r < start or end < l: return 0
if l <= start and end <= r: return self.tree[node]
mid = (start + end) // 2
return (self.query(2*node, start, mid, l, r) +
self.query(2*node+1, mid+1, end, l, r))