전체 글 (28) 썸네일형 리스트형 Segment tree beats (세그 비츠) 4년 전 코포 블로그 글로 올라온 자료구조로, 언젠가부터 웰노운이 된 듯하다. segment tree with lazy propogation을 확장한 형태로, $O(NlogN)$ 혹은 $O(Nlog^2N)$ 정도의 시간복잡도를 가진다. 아이디어 일반적인 레이지 세그트리는 아래와 같이 구현한다. void updseg(int idx, int l, int r, int x, int y, int z) { if (r < x || y < l) return; if (x Propogation 없는 lazy 세그트리 "lazy 세그트리" 자체가 "segment tree with lazy propogation"를 줄여서 부르는 말이기 때문에 propogation이 없다는 것이 다소 이상하기는 하지만, 일부 문제의 경우 세그트리에서 propogation을 lazy하게 하는 것을 넘어서서 아예 하지 않으면 더 효율성을 올릴 수 있다. 시간복잡도는 $O(NlogN)$으로 같다. 이 글에도 같은 내용이 정리되어 있다. 우선 일반적인 lazy 세그트리를 먼저 되짚어보자. 구간 갱신 쿼리와 구간 조회 쿼리(혹은 점 조회 쿼리)가 존재한다. 구간 조회 쿼리에 해당하는 값들을 각 노드에서 들고 있고, $O(logN)$개의 노드를 merge하면 구간 조회 쿼리의 답을 구할 수 있다. 구간 갱신 쿼리는 원래는 $O(N)$개의 노드를 갱.. FWHT (Fast Walsh-Hadamard Transform) 다음 글을 정리한 것이다. https://alan20210202.github.io/2021/07/25/FWHT/ 문제 binary operator $\star$과 수열 $a, b$에 대해 연산 $\circledast$를 아래와 같이 정의하자 $$\{a \circledast b \}_i = \sum_{j \star k = i} {a_j b_k} $$ $\star$가 $+$일 때 이 convolution은 FFT를 이용해 해결할 수 있다. 이제 $\star$가 bitwise or, and, xor인 경우를 해결해보자. 편의상 $a$와 $b$의 길이 $n$은 2의 거듭제곱이라 하자. or convolution은 Fast Mobius Transform이라고도 부르고, xor convolution만을 FWHT라 .. Z 알고리즘 Z 알고리즘이란 문자열 관련 알고리즘으로, Z array를 채우는 알고리즘이다. 길이 $N$의 문자열 $S$가 주어졌을 때 Z array는 아래와 같이 정의된다. $Z[i]:=S$와 $S[i, N - 1]$에 대해 longest common prefix의 길이 이를 $O(N)$에 구할 수 있다. 알고리즘은 KMP와 SA의 중간 정도 느낌이다. $i=1, ..., N-1$에 대해 $Z[i]$를 차례로 구할 것이다. 이때 이전까지 구한 $Z[i]$에 대해, $i+Z[i]$가 최대인 경우의 양 끝점을 기억해두자. ($L=i, R=i+Z[i]-1$) i) $R < i$ 그냥 naive하게 계산하자. 이후 $L$과 $R$ 갱신. ii) $i \le R$ 자명하게 $L < i$이다. $S[0, R - L]$과 $S.. 아호코라식 (Aho-Corasick) 아호코라식은 문자열에서의 패턴 매칭 알고리즘이다. 길이 $N$의 문자열 $S$와 패턴 $T_1, T_2, ..., T_k$($T_i$의 길이는 $M_i$)이 주어졌을 때, 각 패턴이 문자열의 어디에서 나타나는지를 시간복잡도 $O(N+M_1+...+M_k)$만에 찾아낼 수 있다. Naive하게 찾으면 $O(N(M_1+...+M_k))$이고, KMP를 사용하면 $O(Nk+M_1+...+M_k)$라는 점을 감안하면 놀라운 시간복잡도이다. 방법은 KMP+트라이이다. KMP에서는 failure function을 정의했다. 이는 각 prefix $T[0, i-1]$에 대하여, prefix이면서 동시에 suffix인 가장 긴 substring을 나타냈다. failure function을 계산한 후에는, $S$에서 $.. MCMF (Minimum Cost Maximum Flow) 간선마다 유량과 cost가 있는 그래프에서 최대 유량을 구하고, 이 때의 cost를 최소화하는 문제이다. $O(VEf)$로 동작하지만($f$는 최대 유량), SPFA를 사용하면 사실상 $O(Ef)$ 혹은 그보다 빠르게 동작한다. 일반적으로는 문제 모델링에 성공했다면 시간복잡도는 고민하지 않아도 된다. 아이디어는 단순하다. Max flow 문제에서와 마찬가지로 source에서 sink까지의 경로를 찾고, 그 경로를 따라 flow를 흘려주는 과정을 반복하면 된다. 다만 여기서는 minimum cost인 경로(최단 경로)를 찾을 것이다. 유량을 흘린 후에도 나중에 그 유량을 제거해야할 수 있는데, 이를 위해서 유량을 흘릴 때마다 역방향 간선을 만들 것이다. 이 역방향 간선의 cost는 기존 cost와 반대여야.. SPFA (Shortest Path Faster Algorithm) SPFA는 그래프에서 최단 경로를 구하는 알고리즘으로, 중요하게 사용되는 것은 MCMF를 구현할 때이다. 우선 SPFA에 대해 알아보기에 앞서 다른 최단 경로 알고리즘들에 대해 간단하게 살펴보자. 다익스트라 알고리즘은 $O(ElogV)$로 동작하며 (이론적으로는 $O(E+VlogV)$) 음수 간선은 처리할 수 없다. 일반적으로 가장 많이 사용된다. 플로이드-와셜 알고리즘은 $O(V^3)$으로 동작하며, 모든 정점들간의 거리를 모두 구한다는 특징이 있다. 음수 간선이 있어도 잘 동작하며 음수 사이클의 여부를 판단할 수 있다. 벨만-포드 알고리즘은 $O(VE)$이며 음수 간선이 있어도 잘 동작하고, 음수 사이클의 여부를 판단할 수 있다. 이제 SPFA 알고리즘에 대해 알아보자. SPFA 알고리즘은 벨만-포드.. Fenwick Tree (Binary Indexed Tree, BIT) Fenwick Tree (a.k.a. Binary Indexed Tree, BIT)에 대해 알아보도록 하겠다. 펜윅의 기능은 segment tree와 비슷하고, 더 한정적이다. 하지만 비재귀로 쉽게 구현이 가능하고 속도가 훨씬 빠르다. (세그로 짠 $O(logN)$보다 펜윅으로 짠 $O(log^2N)$이 더 빠를 정도.) 그렇기 때문에 펜윅으로 구현이 가능하다면 세그 대신 펜윅을 사용하는 것이 좋다. 수열의 누적합 문제를 풀어보자. 수열 $A[1 ... N]$에 대해 $A[i]$의 값을 바꾸는 점 갱신 쿼리와, 누적합 $A[1] + ... + A[i]$를 구하는 쿼리가 들어온다. 편의상 $N=2^m$이라 하자. 펜윅 $bit[1 ... N]$은 $A$의 구간합에 해당하는 값을 가진다. 구체적으로는, $b.. FFT (Fast Fourier Transform) 문제 $n-1$차 다항식 2개의 곱을 구하는 경우를 생각해보자. $A(x) = a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1}, B(x) = b_0+b_1x+b_2x^2+...+b_{n-1}x^{n-1}, C(x)=A(x)B(x)$ 이를 naive하게 계산하면 $O(n^2)$이지만, FFT를 이용하면 $O(nlogn)$으로 해결할 수 있다. 아이디어 $m-1$차 다항식은 함숫값 $m$개가 결정되면 유일하게 결정된다. 따라서 $x_0, x_1, ..., x_{2m-1}$에 대해 $C(x_i)=A(x_i)B(x_i)$를 모두 구해주면 $2m-1$차 다항식 $C(x)$를 구할 수 있다. 이제 $A(x_i)$와 $B(x_i)$를 빠르게 구하는 방법을 알아보자. 2의 거듭제곱 $n$에 대하여, $n.. Edmond's algorithm (Directed-MST) 먼저 (undirected) MST에 대해 생각해보자. 무향 그래프 $G=(V, E,w)$를 생각하자. ($|V|=N, |E|=M, w:E\to \mathbb{R}$) Spanning Tree란 $G$에서 $N-1$개의 간선을 택해 만든 트리 $T=(V, E'), E'\subseteq E$를 말한다. 이 트리의 가중치는 $w(T)=\sum_{e\in E}{w(e)}$이다. $G$의 spanning tree 중 가중치가 가장 작은 것을 minimum spanning tree(MST)라 한다. MST는 Prim's algorithm 혹은 Kruskal's algorithm을 이용하면 $O(MlogN)$으로 해결할 수 있다. $O(M \alpha (M, N))$인 알고리즘도 존재하지만 PS에서는 잘 쓰이지 않.. KMP(Knuth-Morris-Pratt String Matching Algorithm) KMP는 문자열 매칭(String Matching) 문제를 해결하는 알고리즘이다. 길이가 $N$인 어떤 문자열 $S$와 $S$에서 찾고 싶은 패턴(길이 $M$) $T$가 있을 때, $T$가 $S$에서 몇 번 등장하며 그 위치가 어디인지를 $O(N+M)$에 해결한다. 이러한 문자열 매칭 문제를 푸는 가장 간단한 방법은 $O(NM)$일 것이다. $S$의 각 위치에서 시작하는 substring이 $T$와 일치하는지 확인하는 것이다. KMP 알고리즘은 이 알고리즘에 새로운 아이디어를 추가한다. 바로, 이전에 계산한 정보를 이용할 수 있다는 것이다. $S[i, i+p]$와 $T[0, p]$가 일치하고, $S[i+p+1] \neq [p+1]$이라 하자. 했다고 하자. 그렇다면 $S[j, j+M-1]$과 $T[0, .. Codeforces Round #594 (Div. 1) https://codeforces.com/contest/1239 https://codeforces.com/blog/entry/70720 (Editorial) 원래는 문제를 풀 생각이 아니었지만, 스코더보드의 상태가 흥미로워서(tlwpdus 2등, ainta 4등, D가 B보다 많이 풀림) 문제를 보다가 다 풀어버렸다. A. Ivan the Fool and the Probability Theory $N\times M$크기의 격자가 있다. 이 격자를 검은색과 흰색으로 칠하려고 한다. 이때, 인접한 4칸 중 같은 색인 것이 2개 이상인 칸이 없도록 하려고 한다. 이렇게 칠하는 경우의 수는? 대체적으로 체스판처럼 칠하되, 인접한 두 칸이 같은 색인 경우가 조금씩 있는 형태이다. $(x, y)$와 $(x, y+1.. AGC 039 https://atcoder.jp/contests/agc039/tasks/agc039_a https://img.atcoder.jp/agc039/editorial.pdf (Editorial) 대회는 시간이 안 맞아서 못 쳤고, 나중에 문제만 따로 풀었다. ABCDEF의 6문제가 출제되었고, 150분동안 A B C의 세 문제를 풀었다. A. Connection and Disconnection 문자열 $S$가 주어진다. $S$를 $K$번 반복하여 문자열 $T$를 만든다. $T$의 특정 문자를 다른 문자로 바꾸는 연산을 할 수 있다. $T$에서 인접한 문자들이 서로 다르게 하려고 할 때, 필요한 연산 횟수의 최솟값은? 같은 문자가 반복해서 나오는 부분 문자열을 하나의 구간으로 생각하자. 길이 $x$의 구간에 대.. Suffix Array와 LCP Suffix Array(SA)란 접미사(suffix)들을 정렬해놓은 배열이다. 매우 단순하게 생각하면, 길이가 $1, 2, ..., N$인 suffix를 모두 만든 후 정렬하면 된다. 그러면 $O(N^2logN)$에 구할 수 있다. 그러나 Suffix Array는 $O(N)$ 또는 $O(NlogN)$에 구할 수 있다. 선형 풀이는 복잡하기 때문에 여기서는 $O(NlogN)$만 다루겠다. Suffix Array를 빠르게 구하는 기본 아이디어는, 정렬하려는 문자열들이 서로의 suffix이어서 이전 결과를 이용할 수 있다는 것이다. 길이 $p$까지를 고려하여 suffix들을 정렬한 결과를 가지고 있을 때, 그 값들을 이용하면 길이 $2p$까지를 고려한 결과를 얻을 수 있다. 문자열 $[a, a+2p)$과 문자.. Codeforces Global Round 5 https://codeforces.com/contest/1237 https://codeforces.com/blog/entry/70620 (Editorial) A B C1 C2 D E F G H의 9문제가 나왔는데, 나는 A B까지 푼 후 생각이 막혀서 1시간 반을 버리고 마지막에 C1 C2 D를 풀었다. 레이팅이 100 가까이 떨어져서 Grand master에서 International master가 되었다. A. Balanced Rating Changes 길이가 $N$인 수열 $\{a_0, a_1, ..., a_{N-1}\}$이 주어진다. $\sum a_i=0$이다. $b_i=\lfloor \frac{a_i}{2} \rfloor$ or $b_i=\lceil \frac{a_i}{2} \rceil$, $\.. 이전 1 2 다음
