-
Offline Incremental SCC
본 글에서는 간선이 하나씩 추가됨에 따라 SCC를 관리하는 Incremental SCC를 오프라인으로 처리하는 방법에 대해서 설명하겠습니다. Link Cut Digraph 문제를 보겠습니다. 문제를 간단하게 요약하자면 $N$개의 정점이 있고 $M$개의 간선을 추가하는 쿼리가 있을 때, 간선을 추가할 때마다 u에서 v로 가는 경로가 있고, v에서 u로 가는 경로가 존재하는 (u, v)(u < v, u != v)쌍의 개수를 구하는 문제입니다. 방향 그래프에서 u에서 v로, v에서 u로 갈 수 있다는 것은 u와 v가 서로 같은 SCC에 있다는 것을 의미합니다. 따라서 위...
-
Minimum Cuts in Near-Linear Time
Introduction Weighted graph $G$에 대해, $G$의 min-cut 혹은 edge connectivity 는 $G$의 connected component가 둘 이상이 되도록 하기 위해 제거해야 하는 가중치 합으로 정의됩니다. 이름 그대로 네트워크를 단절시키기 위해 필요한 최소 비용으로, 수많은 파생과 응용이 가능합니다. 이 글에서는 $n$개의 정점, $m$개의 간선을 가진 weighted graph $G$의 min-cut을 near-linear time ($\tilde{O}(m)$)에 구하는 최초의 방법인 D. R. Karger의 Minimum Cuts in Near-Linear Time을 리뷰합니다. Definition 그래프 $G$는 non-negative weighted graph로 가정합니다. 즉, weight는 음 아닌 실수 값을...
-
흥미로운 데이터 추가 모음
개요 2017년 여름 본격적으로 BOJ에서 문제 풀이를 시작한 이래로 저는 많은 문제들에 데이터 추가 요청을 해왔습니다. 조금 사악한 취미일지도 모르겠으나, 문제를 풀어서 ‘맞았습니다!!’를 받는 것 이상으로 즐거웠던 것이 추가한 데이터에 의해 많은 ‘맞았습니다!!’를 받았던 코드들이 ‘틀렸습니다’ 내지는 ‘시간 초과’, 또는 ‘런타임 에러’ 등으로 바뀌는 것을 지켜보는 것이었습니다. 문제를 더 견고하게 만들었다는 뿌듯함과, 많은 분들이 놓쳤을 법한 포인트를 찾아 특이한 형태의 데이터를 제작하는 과정이 즐거웠습니다. 추가한 데이터들 중에는 단순히 기존의 데이터가 빈약해서 그다지 특이할 것 없는...
-
Strassen Algorithm
안녕하세요? 오늘은 행렬을 효율적으로 곱하는 방법과, 그 방법 중 하나이자 분할 정복의 대표적인 예시인 슈트라센 알고리즘(Strassen Algorithm)과 그 구현에 대해 살펴보겠습니다. 모든 예시 코드는 double 형의 $p \times q$크기의 행렬 A와, $q \times r$크기의 행렬 B를 곱하는 기준으로 작성되었습니다. 행렬 곱의 기본 형태 가장 기본적인 행렬 곱의 형태로, 행렬곱은 아래와 같은 코드로 작성됩니다. void matmul(double* a, double* b, double* c, int p, int q, int r) { for (int i = 0; i < p;...
-
그래프의 간선을 제거할 때 절점의 개수를 세는 효율적인 알고리즘
개요 그래프는 일상생활 뿐만 아니라 대부분의 과학 분야에서 ‘추상화’를 위해 사용하는 아주 강력한 자료 구조이다. 그래프의 중요한 성질로 여러 가지가 있으며, 이 글은 그 중에서 특히 절점과 절선에 대하여 다룬다. 무방향 그래프에서 각 간선을 끊었을 때, 그래프의 절점의 개수를 효율적으로 세는 알고리즘에 대하여 알아보고자 한다. 즉, 이 알고리즘은 다음과 같은 일상생활 속 문제를 해결할 수 있게 도와준다: 사내 서버망에서 어떤 회선이 끊어졌다고(불능이 되었다고) 하자. 여기서, 추가적으로 어떤 서버가 고장나야 서버망이 끊기게 되는가. 즉, 어떤 ‘중요한’...