차분 제약 시스템: 그래프 이론으로 푸는 부등식 문제
여러 개의 선형 부등식으로 표현된 제약 조건 하에서 각 변수의 최댓값이나 최솟값을 구해야 할 때, 그래프 이론의 최단경로/최장경로 알고리즘을 활용할 수 있다. 이를 차분 제약 시스템(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에 게시됨