주요 알고리즘 및 자료구조 구현 템플릿 요약
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);
...
9월 19일 12:04에 게시됨
차분 제약 시스템: 그래프 이론으로 푸는 부등식 문제
여러 개의 선형 부등식으로 표현된 제약 조건 하에서 각 변수의 최댓값이나 최솟값을 구해야 할 때, 그래프 이론의 최단경로/최장경로 알고리즘을 활용할 수 있다. 이를 차분 제약 시스템(Difference Constraints System)이라 한다.
핵심 원리: 부등식의 방향성
부등식 xi ≤ xj + ck는 정점 j에서 정점 i로 가는 가중치 ck의 유향 간선으로 해석한다.
목표그래프 해석 ...
7월 11일 02:13에 게시됨
네트워크 유량 알고리즘 구현: 최대 유량과 최소 비용 최대 유량
최대 유량 (Maximum Flow)
최대 유량 문제를 해결하기 위해 가장 널리 사용되는 Dinic 알고리즘의 구현입니다. 너비 우선 탐색(BFS)을 통해 레벨 그래프를 구성하고, 깊이 우선 탐색(DFS)을 통해 블로킹 유량(blocking flow)을 찾아내는 방식을 사용합니다. 현재 엣지 최적화(Current Edge Optimization)가 적용되어 시간 복잡도를 줄였습니다. 가독성과 유지보수를 위해 ...
6월 11일 21:45에 게시됨