알고리즘 경진대회 참가자들은 다양한 알고리즘과 자료구조를 숙지하고 있어야 하며, 이를 효율적으로 구현하기 위해 여러 템플릿을 정리해두는 것이 중요하다.

코드 작성 시 주의사항

• 전역 변수 사용은 피해야 한다. 디버깅이 어렵고 코드의 가독성을 해친다.
• 표준 라이브러리(STL)을 적극 활용하자. 스택, 큐, 벡터 등을 직접 구현하는 것보다 안정적이다.
• #define int long long과 같은 매크로 사용은 권장되지 않는다.

그래프 표현 방식

링크드 리스트 기반 인접 리스트: 메모리 절약이 가능하나 구현이 다소 복잡하다.

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 10;
const int MAX_M = 5e5 + 10;

int node_count, head[MAX_N], distance_array[MAX_N];
struct Edge {
    int next, to, weight;
} edges[MAX_M];

void add_edge(int u, int v, int w) {
    edges[++node_count].next = head[u];
    edges[node_count].to = v;
    edges[node_count].weight = w;
    head[u] = node_count;
}

int main() {
    int n, m, u, v, w;
    cin >> n >> m;
    while(m--) {
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    return 0;
}

벡터 기반 인접 리스트: 구현이 간편하고 STL의 장점을 살릴 수 있다.

#include<bits/stdc++.h>
using namespace std;
const int MAX_M = 5e5 + 10;
int n, m, u, v, w;
vector<pair<int,int>> graph[MAX_M];

int main() {
    cin >> n >> m;
    while(m--) {
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    return 0;
}

인접 행렬: 공간 복잡도가 높아 노드 수가 적을 때만 사용한다.

최단 경로 알고리즘

SPFA (Shortest Path Faster Algorithm):

bool spfa(int start) {
    memset(distance_array, 0x3f, sizeof(distance_array));
    memset(visited, 0, sizeof(visited));
    distance_array[start] = 0;
    queue<int> q;
    q.push(start);
    visited[start] = true;
    count_array[start]++;
    
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        visited[current] = false;
        
        for(auto& edge : graph[current]) {
            int next = edge.first;
            int weight = edge.second;
            
            if(distance_array[next] > distance_array[current] + weight) {
                distance_array[next] = distance_array[current] + weight;
                
                if(!visited[next]) {
                    q.push(next);
                    visited[next] = true;
                    count_array[next]++;
                    
                    if(count_array[next] > n) return false;
                }
            }
        }
    }
    return true;
}

행렬 연산

기본 행렬 곱셈:

#include<bits/stdc++.h>
using namespace std;
int rows_a, cols_a, cols_b;
int matrix_a[110][110], matrix_b[110][110], result[110][110];

int main() {
    cin >> rows_a >> cols_a >> cols_b;
    
    for(int i = 1; i <= rows_a; i++)
        for(int j = 1; j <= cols_a; j++)
            cin >> matrix_a[i][j];
            
    for(int i = 1; i <= cols_a; i++)
        for(int j = 1; j <= cols_b; j++)
            cin >> matrix_b[i][j];
            
    for(int i = 1; i <= rows_a; i++)
        for(int j = 1; j <= cols_b; j++)
            for(int k = 1; k <= cols_a; k++)
                result[i][j] += matrix_a[i][k] * matrix_b[k][j];
                
    for(int i = 1; i <= rows_a; i++) {
        for(int j = 1; j <= cols_b; j++)
            cout << result[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

Floyd-Warshall 알고리즘

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int dist[500][500], n;

int main() {
    // 입력 및 초기화
    memset(dist, 0x3f, sizeof(dist));
    
    // 그래프 구성
    
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                
    return 0;
}

위상 정렬

#include<bits/stdc++.h>
using namespace std;
vector<int> adj_list[5010];
queue<int> q;
int indegree[5010], n;

void topological_sort() {
    for(int i = 1; i <= n; i++) {
        if(indegree[i] == 0) {
            cout << i << " ";
            q.push(i);
        }
    }
    
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        
        for(int neighbor : adj_list[current]) {
            indegree[neighbor]--;
            if(indegree[neighbor] == 0) {
                cout << neighbor << " ";
                q.push(neighbor);
            }
        }
    }
}

최소 공통 조상(LCA)

Binary Lifting 방법:

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 10;
vector<int> tree[MAX_N];
int ancestor[MAX_N][25], depth[MAX_N], n, m, root;

void initialize() {
    for(int j = 1; j <= 20; j++)
        for(int i = 1; i <= n; i++)
            ancestor[i][j] = ancestor[ancestor[i][j-1]][j-1];
}

void dfs(int u, int parent) {
    for(int v : tree[u]) {
        if(v == parent) continue;
        depth[v] = depth[u] + 1;
        ancestor[v][0] = u;
        dfs(v, u);
    }
}

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

최소 신장 트리

Kruskal 알고리즘:

#include<bits/stdc++.h>
using namespace std;
const int MAX_E = 2e6 + 10;
int parent[MAX_E], n, m, edge_count;
long long total_weight;

struct Edge {
    int u, v, weight;
} edges[MAX_E];

int find_parent(int x) {
    if(x == parent[x]) return x;
    return find_parent(parent[x]);
}

bool compare_edges(Edge a, Edge b) {
    return a.weight < b.weight;
}

void kruskal() {
    sort(edges + 1, edges + m + 1, compare_edges);
    
    for(int i = 1; i <= m; i++) {
        int x = find_parent(edges[i].u);
        int y = find_parent(edges[i].v);
        
        if(x == y) continue;
        parent[x] = y;
        total_weight += edges[i].weight;
        edge_count++;
    }
}

Dijkstra 알고리즘 (힙 최적화)

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 10;
priority_queue<pair<int,int>> pq;
int dist[MAX_N], n, m, source;
bool visited[MAX_N];
vector<pair<int,int>> graph[MAX_N];

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

Trie 자료구조

#include<bits/stdc++.h>
using namespace std;
const int MAX_NODES = 3e6 + 10;
int trie[MAX_NODES][65], word_count[MAX_NODES], total_nodes;

int get_index(char c) {
    if(c >= 'A' && c <= 'Z') return c - 'A';
    if(c >= 'a' && c <= 'z') return c - 'a' + 26;
    return c - '0' + 52;
}

void insert_string(char str[]) {
    int current = 0, length = strlen(str);
    
    for(int i = 0; i < length; i++) {
        int index = get_index(str[i]);
        if(trie[current][index] == 0)
            trie[current][index] = ++total_nodes;
        current = trie[current][index];
        word_count[current]++;
    }
}

int search_string(char str[]) {
    int current = 0, length = strlen(str);
    
    for(int i = 0; i < length; i++) {
        int index = get_index(str[i]);
        if(trie[current][index] == 0) return 0;
        current = trie[current][index];
    }
    return word_count[current];
}

세그먼트 트리

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 10;
long long tree[4 * MAX_N], lazy[4 * MAX_N], arr[MAX_N];
int n, m;

void push_up(int node) {
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void build(int node, int start, int end) {
    if(start == end) {
        tree[node] = arr[start];
        return;
    }
    
    int mid = (start + end) / 2;
    build(node * 2, start, mid);
    build(node * 2 + 1, mid + 1, end);
    push_up(node);
}

void push_down(int node, int start, int end) {
    if(lazy[node] == 0) return;
    
    int mid = (start + end) / 2;
    tree[node * 2] += lazy[node] * (mid - start + 1);
    tree[node * 2 + 1] += lazy[node] * (end - mid);
    lazy[node * 2] += lazy[node];
    lazy[node * 2 + 1] += lazy[node];
    lazy[node] = 0;
}

void update_range(int node, int start, int end, int left, int right, long long value) {
    if(left <= start && end <= right) {
        tree[node] += value * (end - start + 1);
        lazy[node] += value;
        return;
    }
    
    push_down(node, start, end);
    int mid = (start + end) / 2;
    
    if(left <= mid) update_range(node * 2, start, mid, left, right, value);
    if(right > mid) update_range(node * 2 + 1, mid + 1, end, left, right, value);
    
    push_up(node);
}

long long query_range(int node, int start, int end, int left, int right) {
    if(left <= start && end <= right) return tree[node];
    
    push_down(node, start, end);
    int mid = (start + end) / 2;
    long long result = 0;
    
    if(left <= mid) result += query_range(node * 2, start, mid, left, right);
    if(right > mid) result += query_range(node * 2 + 1, mid + 1, end, left, right);
    
    return result;
}

이분 탐색

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 10;
int arr[MAX_N], n, target;

bool binary_search_iterative() {
    int left = 1, right = n;
    
    while(left <= right) {
        int mid = (left + right) / 2;
        
        if(arr[mid] == target) return true;
        else if(arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

int lower_bound_custom(int value) {
    int left = 1, right = n, result = n + 1;
    
    while(left <= right) {
        int mid = (left + right) / 2;
        
        if(arr[mid] >= value) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

수학 관련 알고리즘

확장 유클리드 알고리즘:

#include<bits/stdc++.h>
using namespace std;
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 x1, y1;
    ll gcd = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

중국인의 나머지 정리:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_M = 20;
ll moduli[MAX_M], remainders[MAX_M], products[MAX_M], total_product = 1;

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

int main() {
    int n; cin >> n;
    
    for(int i = 1; i <= n; i++) {
        cin >> moduli[i] >> remainders[i];
        total_product *= moduli[i];
    }
    
    for(int i = 1; i <= n; i++) {
        ll x, y;
        products[i] = total_product / moduli[i];
        extended_gcd(products[i], moduli[i], x, y);
        result += remainders[i] * products[i] * (x < 0 ? x + moduli[i] : x);
    }
    
    cout << result % total_product;
    return 0;
}

문자열 알고리즘

KMP 알고리즘:

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 10;
string pattern, text;
int failure_function[MAX_N];

void compute_failure_function() {
    int j = 0;
    for(int i = 1; i < pattern.length(); i++) {
        while(j > 0 && pattern[i] != pattern[j])
            j = failure_function[j - 1];
            
        if(pattern[i] == pattern[j]) j++;
        failure_function[i] = j;
    }
}

void kmp_search() {
    int j = 0;
    for(int i = 0; i < text.length(); i++) {
        while(j > 0 && text[i] != pattern[j])
            j = failure_function[j - 1];
            
        if(text[i] == pattern[j]) j++;
        
        if(j == pattern.length()) {
            cout << i - pattern.length() + 2 << endl;
            j = failure_function[j - 1];
        }
    }
}

동적 계획법

냅색 문제:

// 0-1 Knapsack
#include<iostream>
using namespace std;
int capacity, item_count, weights[110], values[110], dp[1010];

int main() {
    cin >> capacity >> item_count;
    for(int i = 1; i <= item_count; i++)
        cin >> weights[i] >> values[i];
        
    for(int i = 1; i <= item_count; i++)
        for(int j = capacity; j >= weights[i]; j--)
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
            
    cout << dp[capacity];
}