자료구조 완전 정리 2025: Array부터 Trie, B-Tree까지 — 면접에서 쓰이는 모든 자료구조

O(1)        — 상수 시간     예: 배열 인덱스 접근
O(log n)    — 로그 시간     예: 이진 탐색
O(n)        — 선형 시간     예: 배열 순회
O(n log n)  — 선형 로그     예: 머지 소트
O(n^2)      — 이차 시간     예: 버블 소트
O(2^n)      — 지수 시간     예: 피보나치 재귀
O(n!)       — 팩토리얼      예: 순열 생성

n       O(1)  O(log n)  O(n)   O(n log n)  O(n^2)     O(2^n)
10      1     3         10     33          100        1,024
100     1     7         100    664         10,000     1.27e30
1000    1     10        1000   9,966       1,000,000  ---
10000   1     13        10000  132,877     1억         ---

동적 배열 append:
  보통: O(1) — 빈 슬롯에 추가
  가끔: O(n) — 배열 가득 차면 2배 크기로 복사

  n번 append 총 비용: n + n/2 + n/4 + ... ≈ 2n
  상각 비용: O(2n/n) = O(1)

인덱스:  0    1    2    3    4
       [10] [20] [30] [40] [50]
        ^                    ^
     arr[0]              arr[4]

# 동적 배열 구현
class DynamicArray:
    def __init__(self):
        self.size = 0
        self.capacity = 1
        self.data = [None] * self.capacity

    def append(self, value):
        if self.size == self.capacity:
            self._resize(2 * self.capacity)
        self.data[self.size] = value
        self.size += 1

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data
        self.capacity = new_capacity

    def get(self, index):
        if 0 <= index < self.size:
            return self.data[index]
        raise IndexError("Index out of range")

단일 연결 리스트 (Singly):
  [10|→] → [20|→] → [30|→] → [40|→] → None

이중 연결 리스트 (Doubly):
  None ← [←|10|→] ↔ [←|20|→] ↔ [←|30|→] → None

원형 연결 리스트 (Circular):
  [10|→] → [20|→] → [30|→] → [10|→] (처음으로)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, val):
        new_node = ListNode(val, self.head)
        self.head = new_node

    def delete(self, val):
        dummy = ListNode(0, self.head)
        prev, curr = dummy, self.head
        while curr:
            if curr.val == val:
                prev.next = curr.next
                break
            prev, curr = curr, curr.next
        self.head = dummy.next

    def reverse(self):
        prev, curr = None, self.head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        self.head = prev

push(10) → push(20) → push(30) → pop()

  |    |   |    |   | 30 |   | 20 |
  |    |   | 20 |   | 20 |   |    | ← 30 반환
  | 10 |   | 10 |   | 10 |   | 10 |
  +----+   +----+   +----+   +----+

# 스택 — 파이썬 리스트로 구현
class Stack:
    def __init__(self):
        self.items = []

    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):
        return self.items[-1] if self.items else None

    def is_empty(self):
        return len(self.items) == 0

enqueue(10) → enqueue(20) → enqueue(30) → dequeue()

Front →                                    Front →
[10]      [10][20]     [10][20][30]       [20][30]  ← 10 반환

앞에서 삽입/삭제 ← [10][20][30] → 뒤에서 삽입/삭제

key: "apple" → hash("apple") → 3
key: "banana" → hash("banana") → 7
key: "cherry" → hash("cherry") → 3  ← 충돌!

버킷:
[0] →
[1] →
[2] →
[3] → ("apple", 100) → ("cherry", 300)  ← 체이닝
[4] →
[5] →
[6] →
[7] → ("banana", 200)

[3] → ("apple", 100) → ("cherry", 300) → None

선형 탐사(Linear Probing):
  hash("cherry") = 3 → 이미 사용 → 4 확인 → 비어있음 → 저장

이차 탐사(Quadratic Probing):
  hash("cherry") = 3 → 3+1^2=4 → 3+2^2=7 → ...

이중 해싱(Double Hashing):
  hash("cherry") = 3 → 3 + hash2("cherry") → ...

Load Factor = 저장된 요소 수 / 버킷 수

LF > 0.75 → 리해싱 (버킷 수 2배로 확장, 모든 요소 재배치)

class HashMap:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]
        self.load_factor_threshold = 0.75

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        if self.size / self.capacity >= self.load_factor_threshold:
            self._rehash()

        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))
        self.size += 1

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        raise KeyError(key)

    def _rehash(self):
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

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):
        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)
        elif val > node.val:
            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 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

불균형 발생 시 회전(Rotation)으로 균형 복원:

LL 회전 (Right Rotation):      RR 회전 (Left Rotation):
    z                              z
   /                                \
  y         →      y                 y       →      y
 /                 / \                \             / \
x                 x   z                x           z   x

LR 회전:                        RL 회전:
    z                              z
   /                                \
  x         →      y                x       →      y
   \               / \             /               / \
    y             x   z           y               z   x

규칙:
1. 모든 노드는 빨강 또는 검정
2. 루트는 검정
3. 모든 리프(NIL)는 검정
4. 빨강 노드의 자식은 모두 검정 (연속 빨강 불가)
5. 임의 노드에서 모든 리프까지 검정 노드 수 동일

        (B:8)
       /      \
    (R:3)    (R:10)
    / \        \
 (B:1)(B:6)  (B:14)
       / \     /
    (R:4)(R:7)(R:13)

B-Tree (차수 3):
          [10, 20]
         /   |    \
   [3,7]  [12,15] [25,30,40]

B+Tree (차수 3):
          [10, 20]
         /   |    \
   [3,7]  [10,15] [20,25,30]
      ↓ → ↓ → ↓ → ↓ → ↓     ← 리프 노드가 연결 리스트로 연결

배열: [1, 3, 5, 7, 9, 11]

구간 합 Segment Tree:
              [36]           (0-5)
           /        \
        [9]          [27]     (0-2), (3-5)
       /   \        /    \
     [4]   [5]   [16]   [11]  (0-1),(2),(3-4),(5)
    / \          / \
  [1] [3]     [7] [9]

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(arr, 1, 0, self.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
        left = self.query(2 * node, start, mid, l, r)
        right = self.query(2 * node + 1, mid + 1, end, l, r)
        return left + right

Min Heap:                 Max Heap:
      1                        9
     / \                      / \
    3   5                    7   8
   / \ / \                  / \ / \
  7  8 9  10               3  5 4  6

인덱스:  0  1  2  3  4  5  6
Min:   [ 1, 3, 5, 7, 8, 9, 10]

부모: (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):
        if not self.heap:
            raise IndexError("Heap is empty")
        self._swap(0, len(self.heap) - 1)
        val = self.heap.pop()
        if self.heap:
            self._sift_down(0)
        return val

    def _sift_up(self, i):
        parent = (i - 1) // 2
        while i > 0 and self.heap[i] < self.heap[parent]:
            self._swap(i, parent)
            i = parent
            parent = (i - 1) // 2

    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 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 == i:
                break
            self._swap(i, smallest)
            i = smallest

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

def heap_sort(arr):
    import heapq
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

단어: "cat", "car", "card", "dog", "do"

Root
├── c
│   └── a
│       ├── t (*)
│       └── r (*)
│           └── d (*)
└── d
    └── o (*)
        └── g (*)

(*) = 단어의 끝

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 char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    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 autocomplete(self, prefix):
        """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)

그래프:
  A --- B
  |   / |
  |  /  |
  C --- D

인접 리스트 (Adjacency List):
  A: [B, C]
  B: [A, C, D]
  C: [A, B, D]
  D: [B, C]

인접 행렬 (Adjacency Matrix):
     A  B  C  D
  A [0, 1, 1, 0]
  B [1, 0, 1, 1]
  C [1, 1, 0, 1]
  D [0, 1, 1, 0]

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

BFS 순서 (A에서 시작):
Level 0: A
Level 1: B, C
Level 2: D

큐: [A] → [B, C] → [C, D] → [D] → []

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    result = [start]
    for neighbor in graph[start]:
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))
    return result

import heapq

def dijkstra(graph, start):
    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

from collections import deque

def topological_sort(graph, in_degree):
    queue = deque([v for v in graph if in_degree[v] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == len(graph) else []  # 사이클 감지

def bellman_ford(edges, num_vertices, start):
    distances = [float('inf')] * num_vertices
    distances[start] = 0

    for _ in range(num_vertices - 1):
        for u, v, w in edges:
            if distances[u] + w < distances[v]:
                distances[v] = distances[u] + w

    # 음수 사이클 감지
    for u, v, w in edges:
        if distances[u] + w < distances[v]:
            return None  # 음수 사이클 존재

    return distances

처음: 각 노드가 자기 자신을 대표
{0} {1} {2} {3} {4}

union(0, 1): {0, 1} {2} {3} {4}
union(2, 3): {0, 1} {2, 3} {4}
union(0, 3): {0, 1, 2, 3} {4}

find(1) == find(3)?  → Yes (같은 집합)
find(1) == find(4)?  → No (다른 집합)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # 경로 압축 (Path Compression)
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # 랭크 기반 합치기 (Union by Rank)
        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

Level 3: HEAD ────────────────────── 50 ─────── NIL
Level 2: HEAD ──── 20 ──────────── 50 ─── 70 ── NIL
Level 1: HEAD ── 10 ── 20 ── 30 ── 50 ── 70 ── 80 ── NIL
Level 0: HEAD ── 10 ── 20 ── 30 ── 40 ── 50 ── 60 ── 70 ── 80 ── NIL

k=3 해시 함수, m=10 비트 배열

insert("apple"):
  h1("apple")=2, h2("apple")=5, h3("apple")=8
  비트 배열: [0,0,1,0,0,1,0,0,1,0]

query("apple"): 위치 2,5,8 모두 1 → "아마도 있음"
query("grape"): h1=1, h2=5, h3=7 → 위치 1이 0 → "확실히 없음"

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

빠른 삽입/삭제가 중요? → 해시 테이블 또는 연결 리스트
정렬된 순서 필요? → BST 계열 (AVL, Red-Black)
최솟값/최댓값 빠르게? → 힙
문자열 접두사 검색? → 트라이
범위 쿼리? → 세그먼트 트리 또는 B-Tree
집합 소속 빠르게? → 해시셋 또는 블룸 필터
연결 요소 관리? → Union-Find
최단 경로? → 그래프 + Dijkstra/BFS
FIFO? → 큐
LIFO? → 스택