-
플로우 그래프 커팅
개요 Problem Solving을 하다 보면, 주어진 문제에서 플로우 그래프를 모델링했을 때 그래프의 크기가 너무 커서 단순히 플로우 알고리즘을 사용할 경우에 시간 초과를 받게 되는 상황이 종종 발생합니다. 이 글에서는 위와 같은 상황에서 추가적인 관찰을 통해 플로우 그래프의 크기를 줄이는 몇 가지 방법을 소개합니다. 문제마다 필요한 관찰과 해결 방법이 제각기 다를 수 있으므로 다양한 연습 문제를 예시로 들어서 설명하겠습니다. 디닉 알고리즘의 구현체를 통일하기 위해 AtCoder Library의 MaxFlow를 사용하겠습니다. 연습 문제 AtCoder Beginner Contest 320 G. Slot...
-
Deterministic Mincut in Almost-Linear Time
Introduction 지난 3월 포스팅 “Minimum Cuts in Near Linear Time”에서 Weighted min-cut을 near-linear time에 구해주는 Karger의 Monte-Carlo algorithm을 소개한 적이 있었습니다. 이 글에서는 Karger의 알고리즘을 almost-linear complexity로 유지하며 derandomize하는 데 성공한 Jason Li의 2021년 논문 Determinstic Mincut in Almost Linear Time을 리뷰합니다. 논문 자체가 기술적으로 복잡한 부분이 많은 만큼, 깊숙한 디테일을 모두 다루기보다는 특별한 경우에 대해 이 논문에서 소개한 방법론이 어떻게 적용되는지를 다루어보도록 합니다. Terminologies 일부는 3월 포스팅과 동일하지만, Li (2021)의 문법을 대체로 따르면서 변화한...
-
Flow with demands
목차 1. 개요 2. Demands(수요)가 대체 뭐야? 3. Flow with demands 해결법 4. 응용 5. 문제풀이 6. 마무리 7. 참고자료 개요 이번에 소개할 알고리즘은 Flow with demands 입니다. 보통의 간선에 흐를 수 있는 유량에 상한이 있는 최대 유량 문제와 다르게 하한이 있는 최대 유량 문제를 효과적으로 해결하는 알고리즘 이며, 2016년도 한국 ACM-ICPC 예선 H번에서 이 알고리즘을 사용하게 됩니다. 기본적인 아이디어와 작동원리 등을 설명하고 실제로 문제풀이에 어디에 쓰이는지 보이고자 합니다. 일단 기본적으로 최대 유량에 대한 기본...