알고리즘 공부방

1. 모든 $a \leq b$, $c \leq d$에 대해, $f(a, c)+f(b, d) \leq f(a, d)+f(b, c)$가 성립한다면, $f(i, j)$는 사각 부등식 (Quadrangle Inequality), Monge Property를 만족한다. $f(a, c)+f(b, d) \leq f(a, d)+f(b, c)$를 다음과 같이 해석할 수 있다. 구간 $[a, d]$와 $[b, c]$를 선택하는 대신에 구간 $[a, c]$와 $[b, d]$를 선택하도록 바꿔주는 것이 이득이다. 2. $[l, r]$의 값들을 SUM한 함수와 MIN을 취한 함수는 Monge Property를 만족한다. SUM 함수는 항상 $f(a, c)+f(b, d)=f(a, d)+f(b, c)$이니 성립한다. MIN 함수는..

1. 문제에서 구하고 싶은 구조 (트리에서의 경로 / 트리에서의 연속 컴포넌트)를 루트를 정해놓고, 그 루트를 지나는 것들만 고려했을 때 쉽게 풀 수 있다면 Centroid Decomposition을 이용하여 전체 문제를 해결할 수 있다. 만약 트리에서의 루트가 고정되어 있고, 루트를 지나는 구조들에 대해서는 쉽게 풀 수 있다면, 이제 그 루트를 지나지 않는 경우에 대해서는 Centroid Decomposition의 분할정복 과정에서 다음으로 탐색할 것이다. 이와 같이 생각하면 장점이, 루트를 지나는 경로 / 컴포넌트 등은 각 서브트리에서 문제를 독립적으로 해결할 수 있으니, 가능한 모든 정점쌍 / 집합쌍을 고려하는 대신, 한 서브트리의 정점들을 자료구조 안에 삽입한 후 다른 정점들을 빠르게 찾을 수도 ..

www.secmem.org/blog/2019/10/19/handy-function-about-bit/ 1. 비트마스크 S의 가장 마지막 켜져있는 비트 (LSB) 펜윅 트리에 구현에 자주 이용되는 테크닉이다. int lsb=mask&-mask; 2. 비트마스크 S의 부분집합(submask) 모두 순회 $O(2^N)$에 현재 주어진 비트마스크의 모든 부분집합들을 정확히 한번씩만 순회할 수 있다. for(int i=mask; ; i=mask&(i-1)) { if(i==0) break; } 3. 모든 가능한 비트마스크 S에 대해, S의 부분집합(submask) 모두 순회 모든 $O(2^N)$개의 비트마스크를 모두 순회하며, 각 비트마스크에 대해 부분집합을 모두 순회하는데 드는 시간은 $O(3^N)$이다. S에 ..

1. 로그 자료구조의 속도 비교 BIT (Fenwick Tree) < PQ < Set / Map (STL BBST) < Segment Tree < Lazy Segment Tree < Persistent Segment Tree 단, Set/Map은 삽입되는 자료의 양이 커질 때 급격히 느려진다. 2. Locality 다차원 배열의 인덱싱 순서는 반복문 순회 순서와 같게 하는 것이 제일 빠르다. 실제로 실행 시간의 대부분을 차지하는 것은 덧셈, 곱셈 등의 연산이 아니라, 메모리에 접근하고 값을 저장하는 연산이다. 메모리 접근 연산을 할 때에는 최대한 접근하는 위치들이 서로 인접해 있는 것이 좋다. stackoverflow.com/questions/16699247/what-is-a-cache-friendly-..

많은 Tree DP 문제들의 경우, 각 노드에서 특정 시간 복잡도로 노드들을 합치는 작업을 한다. 일반성을 잃지 않고, 노드의 자식이 3개 이상이라면, 더미 노드를 부모 쪽으로 계속 만들어 주며, 모든 트리를 이진 트리 형태로 변형시킬 수 있다. 따라서, 이진 트리에서 자식 노드 두개의 값만을 합쳐주는 문제로 생각한다. 1. $A$, $B$를 합치기 위해서 $sz(A) \cdot sz(B)$의 시간이 필요할 때, 전체 시간복잡도 $O(N^2)$에 합칠 수 있다. (KOI18 검은 돌) $sz(A) \cdot sz(B)$의 값은 왼쪽 자식의 서브트리의 모든 노드와 오른쪽 자식의 모든 서브트리의 노드를 연결했을 때 간선의 수와 같다. 이 때 어떠한 두 정점 $u$, $v$가 합쳐지는 위치는 바로 그 노드의 ..

1. 합이 N인 수들 중 서로 다른 수들의 개수는 최대 $O(\sqrt{N})$개 이다. 서로 다른 수들을 최대한 많이 만들기 위해서는, 모든 수들이 서로 다르고, 1, 2, ... 와 같이 1부터 하나씩 채워 나가는 것이다. $1+2+...+x=N$이니, $x=N$이니, $\sqrt{N}$ 이상의 수들은 많아봤자 $O(\sqrt{N})$개가 된다. $\sqrt{N}$ 이상과 이하인 수들로 나누어 $\sqrt{N}$ 이상인 수들은 그 개수가 $\sqrt{N}$개 이하임을 이용하고, $\sqrt{N}$ 이하인 수들은 그 크기가 $\sqrt{N}$이하임을 이용하여 서로 다른 방법으로 해결할 수 있다.

1. 각 노드에서 light edge를 타고 갈 때마다 서브트리의 크기는 1/2 이하로 감소한다. heavy edge가 가장 서브트리의 크기가 큰 간선이므로, 만약 light edge를 타고 가도 서브트리의 크기가 1/2 초과로 유지된다면, $sz[heavy]>=sz[light]>N/2$, $sz[heavy]+sz[light]>N$으로 모순이다. 2. 각 노드에서 루트 방향으로 부모를 타고 올라갈 때 만나는 light edge의 개수는 $O(logN)$개이다. Property 1에 의해 light edge를 타고 내려가면 서브트리의 크기가 1/2 이하로 감소하니, light edge를 타고 올라가면 서브트리의 크기가 2배 이상으로 증가한다. 전체 트리의 노드의 수가 N개 이니, light edge의 수는..