구사과

Project-TCS 발표 자료 알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 예를 들어서, Heavy Light Decomposition은 트리에서 큰 문제를 부분 문제로 나누는 과정에서 자주 등장한다. 각 문제가 쉽고 (직선), 합치는 것이 가능 (Light edge를 통해서 묶음) 하기 때문이다. 트리의 경우에는 HLD 외에도 다양한 분할 정복 기법이 존재하지만, 그래프를 분할 정복하는 것은 쉽지 않다. 일반적으로, Treewidth와 같이 그래프의 특수한 성질을 요구하는 경우가 많다. 이번에 다룰 Expander Decomposition 은, 그래프의 특수한 성질과..

서울대학교 2020 Div2 C. 넴모넴모 2020 각각의 쿼리에 대해서, $a_x > y$ 이면 답은 자명히 0입니다. 아니면, $a_j \le y$ 를 만족하는 최소 $j$ 를 찾음으로써 간단한 수식으로 문제를 해결할 수 있습니다. 이러한 $j$는 이진탐색을 사용하여 찾으면 됩니다. VKOShP 2017 D. Equal Maximums 두 구간이 공통으로 가지는 최댓값 $X$ 를 고정하고 문제를 해결해 봅시다. $X$ 의 등장 위치를 배열에 모두 마킹하면, 두 구간은 $X$ 를 하나 이상 포함하는 겹치지 않는 구간의 모습을 보입니다. 왼쪽 구간에서 가장 오른쪽에 등장하는 $X$ ($X_1$ 로 표기합니다.), 오른쪽 구간에서 가장 왼쪽에 등장하는 $X$ ($X_2$ 로 표기합니다.) 를 고릅시다. 이..

ABC 159 A. The Number of Even Pairs $N(N-1)/2+M(M-1)/2$ 를 출력하시면 됩니다. ABC 159 E. Dividing Chocolate 가로로 초콜릿을 자를 수 있는 모든 $2^{N-1}$ 개의 경우를 다 시도해 봅시다. 세로로 자를 때는 그리디 알고리즘을 사용할 수 있습니다. 왼쪽에서 오른쪽으로 순서대로 봅니다. $K$ 초과의 초콜릿이 생기지 않을 때까지 최대한 초콜릿을 자르지 않고, $K$ 초과의 초콜릿이 생기면 그 전 지점에서 잘라줍니다. 이 알고리즘은 가로로 자르는 방법이 고정되어 있을 때 최적이며, $O(NM)$ 에 구현할 수 있습니다. 고로 시간 복잡도는 $O(2^N NM)$ 입니다. ARC 110 A. Redundant Redundancy 나머지가 모..