-
rdd6584's profile image
rdd6584
June 21, 2021
오일러 지표와 문제 풀이
평면 연결 그래프에서 $V$와 $E$를 각각 정점과 간선의 집합 $f$를 면의 개수라고 할 때, $|V|-|E|+f=2$라는 공식이 성립하고 우리는 흔히 이를 오일러 지표라고 부릅니다. 여기서 면은 outer face, 즉, 무한히 바깥으로 뻗어나가는 면을 포함합니다. 위의 그래프에서도 이 식이 성립함을 관찰하실 수 있습니다. 평면 연결 그래프 $G$에서 $|V|-|E|+f=2$라는 사실을 귀납법을 이용하여 증명해봅시다. 우선 임의의 트리는 항상 $|V|-|E|=1$ 이므로, 이 공식이 성립함을 쉽게 보일 수 있습니다. 만약 그래프가 트리가 아닌 경우, 임의의 사이클이 존재하고. 사이클을 구성하는 임의의 간선은...
-
rdd6584's profile image
rdd6584
May 20, 2021
Parallel Binary Search
이 게시글은 이분 탐색에 대한 지식을 필요로 합니다. 그리고 union-find, segment tree 자료구조에 대해 알고 있으면 좋습니다. 아래 문제를 봅시다. 제한된 메모리(링크) 길이 $N$의 배열 $A$에서, $q$번째로 작은 원소를 구하는 쿼리를 여러 번 해결하는 문제입니다. 하지만, 문제 지문에 나와 있듯이, 이 문제의 메모리 제한은 4MB로 $A$에 대한 메모리를 할당할 수 없습니다. 하나의 쿼리에 대해 해결해 봅시다. $f(a) =$ 배열 $A$에서 $a$ 이하인 수의 개수라고 합시다. $f(a) \geq q+1$인 경우, $q$번째로 작은 원소는 $a$ 이하입니다. 함수...
-
rdd6584's profile image
rdd6584
March 24, 2021
Segment의 개수를 이용하는 순열 경우의 수 문제
소개 특정 조건을 만족하는 순열의 개수를 세는 문제 중에서, segment(이하 구간)의 개수를 이용하는 특이한 꼴의 다이나믹 프로그래밍 문제를 다뤄보려고 합니다. 예시 문제를 통해 살펴봅시다. 문제1. 길이가 $N$, Increasing segment의 개수가 $K$개인 순열의 개수 Increasing segment란, $l+1 \leq i \leq r$인 모든 $i$에 대해 $A_{i-1} < A_i$를 만족하는 $[l, r]$이라고 합니다. 단, 다른 increasing segment에 포함되는 구간은 무시하는 걸로 합시다. 예를 들어, $1\space4\space5\space2\space3\space6\space8\space7$의 increasing segment는 $[1, 3], [4, 7], [8, 8]$로 총 3개입니다. 우리는 길이가 $N$이고...
-
rdd6584's profile image
rdd6584
January 19, 2020
Rabin fingerprint for problem solving
Rabin fingerprint란? Rabin fingerprint는 길이 $n$의 배열 $m$, 임의의 값 $\space x$에 대해 아래와 같은 수식을 가지는 일종의 해시 함수입니다. $f(x)=m_{0}+m_{1}x+\ldots +m_{n-1}x^{n-1}$ 주로, 라빈카프 알고리즘에서 사용되기 때문에 해당 알고리즘을 공부하신 분께는 친숙할텐데요. 위 해시함수를 응용하여 문제를 해결하는 방법에 대해서 소개하고자 합니다. 모든 설명에서 $x$가 $max(m_i)$보다 큰 상황을 가정합니다. 가장 긴 문자열(링크) $m_0$ ~ $m_i$를 $g(x,\space 0,\space i) = m_0 + m_1x + … + m_{i}x^{i}$와 같이 $m_j$ ~ $m_{j+i}$를 $g(x,\space j,\space j+i) = (m_jx^{j} +...
-
rdd6584's profile image
rdd6584
December 17, 2019
Mo's Algorithm on Trees
이 게시글은 LCA(lowest common ancestor)에 대한 지식이 선행되어야 하지만 본 글에서는 소개하지 않습니다. Mo’s Algorithm이란? Mo’s algorithm은 평방 분할(sqrt decomposition)의 일종의 활용 기법으로, 오프라인으로 구간 쿼리 문제를 해결할 때 사용할 수 있습니다. 이미 이에 관한 좋은 글이 있어 (링크)로 대체하겠습니다. Mo’s Algorithm on Trees? 위 Mo’s Algorithm을 Tree에서 하는 것을 의미합니다. Mo’s는 앞서 말씀드렸던 것처럼 구간 쿼리 문제를 해결할 때 쓰이기 때문에 트리에서의 쿼리를 구간 쿼리처럼 나타낼 필요가 있는데요. 이를 Euler Tour on Trees를 이용하여...
-
rdd6584's profile image
rdd6584
November 16, 2019
Exchange argument
Exchange argument란? 임의의 상태에서 매순간 손해보지 않으면서, 원소끼리의 교환을 통해 얻어지는 상태로 나아가는 것을 반복하면 최적의 상태를 얻을 수 있다는 탐욕적인 주장입니다. 이해를 위해 다양한 문제에서의 활용을 소개해보겠습니다. 구두 수선공(링크) 우리는 주어지는 작업의 순서를 정해서 최적의 작업순서를 정해야 합니다. 임의의 작업 순서가 정해졌을 때 비용은 $ (T_{k_1}) \times S_{k_2} + (T_{k_1}+T_{k_2}) \times S_{k_3} + … (T_{k_1}+T_{k_2}+…T_{k_{n_-1}}) \times S_{k_n} $ 이 됩니다. 여기서 $ i $ 번째와 $ i+1 $ 번째의 작업의 순서를 서로 바꾸는 시행에...
-
rdd6584's profile image
rdd6584
October 19, 2019
Segment Tree Beats
안녕하세요. rdd6584로 활동하고 있는 권일우입니다. 이 글에서는 요즘 유행하는 segment tree beats(이하 세그비츠)에 대해서 소개하겠습니다. 이를 위해서는, segment tree with lazy propagation에 대한 지식이 선행되어야 하지만 여기서는 소개하지 않겠습니다. Segment Tree Beats segment tree beats의 beats는 일본 애니메이션 “angel beats”에서 따온 것으로 특별한 의미를 가지고 있지 않습니다. 그러면 세그비츠가 뭘까요? 세그비츠는 lazy propagation의 활용형으로 중단조건과 갱신조건을 적절히 조절하여 까다로운 구간 쿼리를 해결하는 방법 중 하나입니다. 아래와 같은 문제가 있습니다. 길이 $N$의 배열 $A$, 아래와 같은...