---

컴퓨터 과학을 깊이 이해하고 싶은 사람이라면, 특정 알고리즘과 자료구조는 반드시 숙지해야 한다. 오늘은 그 중에서도 중요한 10개를 꼽아 원리와 함께 파이썬 코드 예시까지 정리한다. 이 글을 통해 각 알고리즘의 쓰임새, 시간 복잡도, 기본 개념을 명확히 이해할 수 있을 것이다.

1. Dijkstra 알고리즘

Dijkstra는 그래프에서 하나의 시작 노드로부터 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 음수 간선이 없는 경우에만 정확히 동작한다.
핵심 아이디어는 “가장 가까운 노드부터 탐색하면서 거리를 갱신”하는 그리디 전략이다.

import heapq

def dijkstra(graph, start):
    INF = float('inf')
    distances = {node: INF for node in graph}
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_dist, current_node = heapq.heappop(queue)

        if current_dist > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

2. Bellman-Ford 알고리즘

Bellman-Ford는 Dijkstra와 유사하지만, 음수 간선이 있어도 동작할 수 있다. 반복적으로 모든 간선을 탐색하여 거리를 업데이트한다.
특히, 음수 사이클이 존재하는지도 감지할 수 있다는 점이 큰 강점이다.

def bellman_ford(edges, V, start):
    INF = float('inf')
    dist = {v: INF for v in range(V)}
    dist[start] = 0

    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    return dist

3. Floyd-Warshall 알고리즘

Floyd-Warshall은 모든 정점 쌍 간의 최단 거리를 한 번에 구하는 알고리즘이다. 동적 계획법의 대표 사례로, 경유지를 하나씩 추가하는 방식으로 거리를 갱신한다.
다소 느리지만 전체 거리 테이블을 구축해야 할 때 매우 유용하다.

def floyd_warshall(graph, V):
    dist = [[float('inf')] * V for _ in range(V)]
    for u in range(V):
        dist[u][u] = 0
    for u, v, w in graph:
        dist[u][v] = w

    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

4. SPFA 알고리즘

**SPFA(Shortest Path Faster Algorithm)**는 Bellman-Ford를 큐 기반으로 최적화한 알고리즘이다. 평균적으로 매우 빠르며, 음수 간선을 허용한다.

from collections import deque, defaultdict

def spfa(graph, start, V):
    INF = float('inf')
    dist = [INF] * V
    in_queue = [False] * V
    dist[start] = 0

    queue = deque([start])
    in_queue[start] = True

    while queue:
        u = queue.popleft()
        in_queue[u] = False

        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True

    return dist

5. Prim 알고리즘

Prim은 최소 신장 트리를 구하는 대표 알고리즘이다. 하나의 정점에서 시작해, 가장 가까운 정점을 연결하는 방식으로 전체 트리를 만들어간다.
다익스트라와 방식이 비슷해 헷갈리기 쉽다.

import heapq

def prim(graph, V):
    mst = []
    visited = [False] * V
    pq = [(0, 0, -1)]  # (cost, node, parent)

    while pq:
        cost, u, parent = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        if parent != -1:
            mst.append((parent, u, cost))

        for v, weight in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (weight, v, u))

    return mst

6. Kruskal 알고리즘

Kruskal은 최소 신장 트리를 만드는 또 다른 방법으로, 간선을 가중치 순으로 정렬하여 선택하고, 사이클을 방지하기 위해 Union-Find를 사용한다.

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, rank, u, v):
    root_u = find(parent, u)
    root_v = find(parent, v)

    if root_u != root_v:
        if rank[root_u] > rank[root_v]:
            parent[root_v] = root_u
        elif rank[root_u] < rank[root_v]:
            parent[root_u] = root_v
        else:
            parent[root_v] = root_u
            rank[root_u] += 1

def kruskal(edges, V):
    edges.sort(key=lambda x: x[2])
    parent = [i for i in range(V)]
    rank = [0] * V
    mst = []

    for u, v, weight in edges:
        if find(parent, u) != find(parent, v):
            union(parent, rank, u, v)
            mst.append((u, v, weight))

    return mst

7. Trie (트라이)

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 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.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

8. Binary Search (이분 탐색)

Binary Search는 정렬된 배열에서 원하는 값을 O(log⁡N)O(\log N) 시간에 찾을 수 있다. 탐색 대상이 정렬되어 있을 때 최적의 검색 기법이다.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

9. Hashing (해싱)

Hashing은 키-값 쌍을 저장하고 검색하는 기술이다. 해시 함수를 통해 평균 O(1)O(1) 시간에 접근할 수 있으며, 충돌이 발생하면 체이닝이나 오픈 어드레싱으로 해결한다.
파이썬에서는 dict가 대표적인 해시 자료구조다.

# 기본적인 dict 사용 예시
hash_table = {}
hash_table["apple"] = "red"
hash_table["banana"] = "yellow"
print(hash_table.get("apple"))  # red

10. Rabin-Karp Fingerprinting

Rabin-Karp는 문자열 검색 알고리즘으로, 해시값을 이용해 부분 문자열 비교를 빠르게 수행한다. 해시 충돌이 발생할 수 있어 추가 검증이 필요하지만, 여러 패턴을 동시에 검색할 때 강력하다.

def rabin_karp(text, pattern):
    d = 256
    q = 101
    M = len(pattern)
    N = len(text)
    h = 1
    p = 0
    t = 0

    for i in range(M - 1):
        h = (h * d) % q

    for i in range(M):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q

    for i in range(N - M + 1):
        if p == t:
            if text[i:i + M] == pattern:
                return i
        if i < N - M:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + M])) % q
            if t < 0:
                t += q
    return -1

---

이상의 10개 알고리즘과 자료구조는 실전 문제 풀이, 코딩 테스트, 그리고 고급 시스템 구현까지 폭넓게 활용된다. 각 개념과 코드를 반복적으로 연습하고, 자신만의 방식으로 최적화해보는 과정이 중요하다.