구사과

Petrozavodsk Winter 2020 Day9D. Data Structure Quiz $O((n + q_1 + q_2) \log^2 n)$ 풀이도 있고, $O(n^{5/3} + (q_1 + q_2) n^{1/3} \log n)$ 풀이도 있습니다. 두 번째는 통과를 하고, 첫 번째는 구현은 안 해 봤지만 아마 통과를 못 할 것 같습니다 :) 여기서는 $O((n + q_1 + q_2) \log^2 n)$ 풀이를 소개한 후 $O((n + q_1) \log^2 n + q_2 \log n)$ 풀이를 소개합니다. $x, y$ 축에 대한 2차원 세그먼트 트리 같은 것을 사용할 수 없으니, $x$ 축은 분할 정복, $y$ 축은 1차원 세그먼트 트리를 사용해서 관리하는 식의 접근을 사용합니다. 전반적인 철학은 O..

POI 1996. Canoes 먼저 각각의 사람을 몸무게 순으로 정렬해 놓읍시다. 가장 가벼운 사람은 다른 사람과 보트를 태워 보내는 것이 합리적으로 보이니, 가장 가벼운 사람을 보낼 때는, 다른 사람 한 명을 잡아서 같이 보트를 태워 보냅니다. 같이 탈 수 있는 사람이 여럿이면 물론 몸무게가 무거운 사람을 보내는 것이 현명합니다. 두 번째, 세 번째로 가벼운 사람들에게 이를 반복하고, 같이 태워 보낼 수 있는 사람이 없을 때까지 이를 반복합니다. 이 알고리즘의 구현은, 정렬된 배열에서 현재 보낼 무거운 사람의 “포인터” 를 가지고 있으면 간편합니다. 가벼운 사람이 있을 때, 이 사람의 몸무게를 맞출 수 있을 때까지 포인터를 앞으로 (몸무게가 감소되는 쪽으로) 내려주고, 그 사람과 매칭시킨 후, 포인터를..

(Lecture note is essentially an English version of this post. Slides are used for presentation.) 원 논문 (arxiv) 그래프의 최소 컷 (Minimum cut) 은 그래프를 연결되지 않게 하기 위해서 지워야 하는 간선 가중치의 최소 합이다. 가중치가 없는 경우에, 최소 컷은 그래프의 connectivity 를 정의하는 수량이 된다. 고로 최소 컷은 그래프가 주어졌을 때 계산하고 싶은 가장 기초적인 수량에 해당되며, 응용 예시 또한 무수히 많다. 그래프의 최소 컷을 계산하는 방법은 크게 3가지가 있다. 아래에 해당 방법의 발견 시간 순으로 나열한다. (아래 요약은 이 논문에서 따왔다.) Min-cut Max-flow 접근. Gl..