-
Disjoint Set & Union-find
Disjoint Set Disjoint Set(서로소 집합, 분리 집합)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말합니다. 모든 집합들 사이에 공통된 원소가 존재하지 않는다는 것을, 각 원소들은 하나의 집합에만 속함을 의미하므로, 모든 원소들은 자신이 속해있는 유일한 집합만을 가지게 됩니다. Disjoint set data structure를 사용하면 서로 다른 원소들이 같은 집합에 속해있는지, 혹은 속해있지 않은지를 판별하는데에 유용히 사용할 수 있습니다. 이를 활용하기 위해서는 Disjoint Set Union(DSU, 분리합집합) 자료구조를 만들 수 있어야 한다. 정의에 의해 Disjoint Set...
-
Ray Casting Algorithm의 이분 탐색을 이용한 응용
Ray Casting Algorithm (단순) 다각형과 점이 주어졌을 때, 점이 다각형 안에 있는지 판정하는 문제는 계산 기하학뿐 아니라 컴퓨터 그래픽스에서도 중요한 문제이다. 이를 해결하는 대표적인 알고리즘이 Ray casting algorithm이다. 가장 간단한 버전의 ray casting algorithm은 다음과 같은 문제를 푸는 데 사용된다. “2차원 좌표평면 위에 단순 다각형 $(x_0, y_0), \cdots, (x_N, y_N)$이 있다. 마찬가지로 2차원 좌표평면 위에 점 $P=(x, y)$가 주어질 때, 이 점이 다각형 안에 있는지 밖에 있는지 판정하라.” Ray casting algorithm은 이를 다음과 같은 아이디어로...
-
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에서 문제 풀이를 시작한 이래로 저는 많은 문제들에 데이터 추가 요청을 해왔습니다. 조금 사악한 취미일지도 모르겠으나, 문제를 풀어서 ‘맞았습니다!!’를 받는 것 이상으로 즐거웠던 것이 추가한 데이터에 의해 많은 ‘맞았습니다!!’를 받았던 코드들이 ‘틀렸습니다’ 내지는 ‘시간 초과’, 또는 ‘런타임 에러’ 등으로 바뀌는 것을 지켜보는 것이었습니다. 문제를 더 견고하게 만들었다는 뿌듯함과, 많은 분들이 놓쳤을 법한 포인트를 찾아 특이한 형태의 데이터를 제작하는 과정이 즐거웠습니다. 추가한 데이터들 중에는 단순히 기존의 데이터가 빈약해서 그다지 특이할 것 없는...