KMP 문자열 매칭 (KMP Pattern Matching)

패턴 문자열 내의 접두사와 접미사가 일치하는 최대 길이를 계산하여 불필요한 비교를 줄이는 알고리즘입니다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> compute_pi(const string& p) {
    int m = p.size();
    vector<int> pi(m, 0);
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && p[i] != p[j]) j = pi[j - 1];
        if (p[i] == p[j]) pi[i] = ++j;
    }
    return pi;
}

void kmp(const string& s, const string& p) {
    vector<int> pi = compute_pi(p);
    int n = s.size(), m = p.size();
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && s[i] != p[j]) j = pi[j - 1];
        if (s[i] == p[j]) {
            if (j == m - 1) {
                cout << i - m + 2 << "\n";
                j = pi[j];
            } else j++;
        }
    }
    for (int x : pi) cout << x << " ";
}

트라이 (Trie)

문자열 집합을 효율적으로 저장하고 검색하기 위한 트리 구조입니다.

#include <cstring>

const int MAX_NODES = 100000;
int trie_nodes[MAX_NODES][26], is_end[MAX_NODES], node_count = 1;

void insert_word(char* str) {
    int curr = 1;
    for (int i = 0; str[i]; i++) {
        int ch = str[i] - 'a';
        if (!trie_nodes[curr][ch]) trie_nodes[curr][ch] = ++node_count;
        curr = trie_nodes[curr][ch];
    }
    is_end[curr] = 1;
}

bool search_word(char* str) {
    int curr = 1;
    for (int i = 0; str[i]; i++) {
        curr = trie_nodes[curr][str[i] - 'a'];
        if (!curr) return false;
    }
    return is_end[curr];
}

희소 테이블 (Sparse Table - ST Table)

정적인 배열에서 구간 쿼리(RMQ 등)를 O(1)에 처리하기 위한 자료구조입니다. 초기화 시 log 연산의 정밀도에 주의해야 합니다.

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAXN = 100005;
int st[MAXN][20], logs[MAXN];

void build_st(int n, int* arr) {
    logs[1] = 0;
    for (int i = 2; i <= n; i++) logs[i] = logs[i / 2] + 1;
    for (int i = 1; i <= n; i++) st[i][0] = arr[i];
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int L, int R) {
    int j = logs[R - L + 1];
    return max(st[L][j], st[R - (1 << j) + 1][j]);
}

최단 경로 알고리즘 (Dijkstra & SPFA)

그래프 내에서 단일 시작점 최단 경로를 구하는 알고리즘들입니다.

Dijkstra (우선순위 큐 이용)

#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;
vector<pair<int, int>> adj[500005];
int dist[500005];

void dijkstra(int start) {
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pair<int, int>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        int d = -pq.top().first;
        int curr = pq.top().second;
        pq.pop();
        if (d > dist[curr]) continue;
        for (auto& edge : adj[curr]) {
            int next = edge.first, weight = edge.second;
            if (dist[next] > dist[curr] + weight) {
                dist[next] = dist[curr] + weight;
                pq.push({-dist[next], next});
            }
        }
    }
}

SPFA

void spfa(int start, int n) {
    memset(dist, 0x3f, sizeof(dist));
    vector<bool> in_queue(n + 1, false);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    in_queue[start] = true;
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        in_queue[curr] = false;
        for (auto& edge : adj[curr]) {
            int next = edge.first, weight = edge.second;
            if (dist[next] > dist[curr] + weight) {
                dist[next] = dist[curr] + weight;
                if (!in_queue[next]) {
                    q.push(next);
                    in_queue[next] = true;
                }
            }
        }
    }
}

확장 유클리드 알고리즘 (Extended GCD)

두 정수 a, b에 대해 ax + by = gcd(a, b)를 만족하는 정수해 x, y를 구합니다.

typedef long long ll;
ll extended_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

최소 공통 조상 (LCA)

트리 구조에서 두 노드의 공통된 조상 중 가장 낮은 노드를 찾는 알고리즘입니다.

희소 테이블을 이용한 배증법 (Binary Lifting)

int parent[MAXN][22], depth[MAXN];
void dfs_lca(int curr, int p, int d) {
    depth[curr] = d;
    parent[curr][0] = p;
    for (int i = 1; i <= 20; i++)
        parent[curr][i] = parent[parent[curr][i - 1]][i - 1];
    for (int next : tree_adj[curr]) {
        if (next != p) dfs_lca(next, curr, d + 1);
    }
}

int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = 20; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) u = parent[u][i];
    }
    if (u == v) return u;
    for (int i = 20; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[u][0];
}

최소 신장 트리 (Kruskal's Algorithm)

간선들을 가중치 기준으로 정렬한 뒤, 유니온 파인드를 이용해 사이클을 형성하지 않는 간선들을 선택합니다.

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const { return w < other.w; }
};

int find_root(int x, int* parent) {
    return parent[x] == x ? x : parent[x] = find_root(parent[x], parent);
}

int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    int parent[MAXN], mst_weight = 0;
    for (int i = 1; i <= n; i++) parent[i] = i;
    for (auto& e : edges) {
        int root_u = find_root(e.u, parent);
        int root_v = find_root(e.v, parent);
        if (root_u != root_v) {
            parent[root_u] = root_v;
            mst_weight += e.w;
        }
    }
    return mst_weight;
}

펜윅 트리 (Binary Indexed Tree)

구간 합과 데이터 업데이트를 로그 시간에 수행하는 효율적인 구조입니다.

int bit[MAXN], n;
void update(int idx, int val) {
    for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
int query_sum(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx) res += bit[idx];
    return res;
}

세그먼트 트리 (Segment Tree)

Lazy Propagation을 활용하여 구간 업데이트와 구간 쿼리를 수행합니다.

struct Node {
    int l, r;
    long long sum, lazy;
} tree[MAXN * 4];

void push_up(int p) {
    tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}

void push_down(int p) {
    if (tree[p].lazy) {
        int mid = (tree[p].l + tree[p].r) >> 1;
        tree[p << 1].sum += tree[p].lazy * (mid - tree[p].l + 1);
        tree[p << 1 | 1].sum += tree[p].lazy * (tree[p].r - mid);
        tree[p << 1].lazy += tree[p].lazy;
        tree[p << 1 | 1].lazy += tree[p].lazy;
        tree[p].lazy = 0;
    }
}

void update_range(int p, int L, int R, int val) {
    if (L <= tree[p].l && tree[p].r <= R) {
        tree[p].sum += (long long)val * (tree[p].r - tree[p].l + 1);
        tree[p].lazy += val;
        return;
    }
    push_down(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (L <= mid) update_range(p << 1, L, R, val);
    if (R > mid) update_range(p << 1 | 1, L, R, val);
    push_up(p);
}

평형 이진 탐색 트리 (Splay Tree)

Splay 연산을 통해 자주 접근하는 노드를 루트로 옮겨 성능을 최적화하는 트리입니다.

struct SplayTree {
    int ch[MAXN][2], fa[MAXN], cnt[MAXN], size[MAXN], val[MAXN];
    int root, tot;

    void update(int x) {
        size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
    }

    bool get_dir(int x) { return x == ch[fa[x]][1]; }

    void rotate(int x) {
        int y = fa[x], z = fa[y];
        int k = get_dir(x);
        ch[y][k] = ch[x][k ^ 1];
        fa[ch[x][k ^ 1]] = y;
        ch[z][get_dir(y)] = x;
        fa[x] = z;
        ch[x][k ^ 1] = y;
        fa[y] = x;
        update(y); update(x);
    }

    void splay(int x, int goal = 0) {
        while (fa[x] != goal) {
            int y = fa[x], z = fa[y];
            if (z != goal)
                (get_dir(x) == get_dir(y)) ? rotate(y) : rotate(x);
            rotate(x);
        }
        if (!goal) root = x;
    }
};