-
Stoer-Wagner Algorithm
안녕하세요? 오늘은 Stoer-Wagner 알고리즘에 대해 살펴보겠습니다. Stoer-Wanger 알고리즘은 그래프의 Global Minimum Cut을 찾는 알고리즘입니다. Introduction 그래프를 두 집합 $S$, $T$로 나누는 것을 그래프의 cut이라고 합니다. 간선에 weight가 있는 그래프에서, 두 점 $s$와 $t$가 주어졌을 때 $s \in S$, $t \in T$를 만족하도록 그래프를 cut하는 상황을 생각해봅시다. 한 쪽 노드는 집합 $S$에, 다른 한 쪽은 $T$에 포함된 모든 edge들의 weight의 합을 cut의 크기라고 합니다. 이 때 크기가 가장 작은 최소 cut은 최대 유량과 같다는 사실(Min-cut Max-flow...
-
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)의 문법을 대체로 따르면서 변화한...
-
2-connectivity
Connectivity Problem $k+1$개 이상의 정점을 가진 그래프 $G$가 임의의 $k-1$개의 정점을 제거하더라도 남은 그래프가 connected graph를 유지한다면 그래프 $G$를 k-vertex-connected 라고 합니다. 이때 이를 만족하는 $k$ 중 가장 큰 값을 $G$ 의 vertex connectivity 라고 합니다. 비슷한 방식으로 간선의 경우도 $k-1$개의 간선을 제거하더라도 남은 그래프가 connected graph인 경우 k-edge-connected 라고 표현하고, 그중 가장 큰 $k$ 를 $G$의 edge connectivity 라고 합니다. 아래 그림은 2-vertex-connected 그래프의 예시입니다. 어떤 정점을 삭제하더라도 남은 그래프가 연결 그래프로 유지되기 때문입니다....
-
2020년 선린인터넷고등학교 교내 프로그래밍 대회들의 풀이
작년 하반기에 선린인터넷고등학교에서 개최되는 여러 정보 경시 대회에 김준원, 권욱제님 등과 함께 출제했던 적이 있습니다. 이 대회들에는 여러 교육적인 문제가 많이 있었으나, 잘 정리된 풀이는 아직 없는 것 같아서 이 참에 정리해봤습니다. 1. 2020 선린 정보 알고리즘경시대회 문제는 https://www.acmicpc.net/category/detail/2294 에서 풀어볼 수 있습니다. A. 헛간 청약 지문을 잘 읽으면 해결할 수 있는 문제다. 정답은 $\min(N, \lfloor W/L \rfloor \times \lfloor H/L \rfloor)$ 이다. 정답이 최대 $N$ 임에 유의하여 해결해야 합니다. B. 소-난다! 비트마스킹을 이용하여 $2^N$개의...
-
testlib 사용하기
개요 testlib는 Polygon에서 프로그래밍 문제를 만들기 위한 유틸리티를 한데 모아놓은 라이브러리입니다. Generator, validator, checker 및 interactor 제작에 공통적으로 사용되며, 신뢰도 높은 랜덤 함수, 안정성 있으며 정규표현식을 지원하는 문자열 파싱, Polygon 및 채점 시스템과의 상호작용 등의 다양한 기능을 갖추고 있으며 Polygon과 GitHub 페이지에서 다양한 사용 예제들도 제공해 줍니다. 문제 출제를 위한 플랫폼 - Polygon 사용하기 글에 간단한 사용 예시가 나와있습니다. 유용한 기능을 많이 갖추고 있고 코드의 주석 또한 훌륭한 반면에 testlib에 대한 별도의 문서화는 이루어지지 않았습니다....