본문 바로가기

알고리즘

(16)
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 알고리즘은 벨만-포드..
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, ..
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)$과 문자..
양수 가중치를 가지는 그래프에서 O(V+cE)로 최단경로 구하기 가중치가 없는, 혹은 모든 간선의 가중치가 1인 그래프에서는 BFS를 이용하면 $O(V+E)$로 최단경로를 구할 수 있다. 이를 응용하여, 가중치가 $c$ 이하의 자연수인 그래프에서 최단경로를 구하자. 가중치 $c$의 간선을, 가중치 $1$의 간선 $c$개로 나누자. 그러면 새로운 노드가 $c-1$개가 생길 것이다. 그러고 나면 간선이 $O(cE)$개, 정점이 $O(V+cE)$개인 그래프가 된다. 여기서 BFS를 통해 최단경로를 구하면 $O(V+cE)$로 최단경로를 구할 수 있다. 이 방법은 $c$가 작을 때 유용하다. https://www.geeksforgeeks.org/shortest-path-weighted-graph-weight-edge-1-2/ 참고. 내 코드 #include using name..
0-1 BFS 가중치가 없는, 또는 모든 간선의 가중치가 1인 그래프를 생각하자. 그러한 그래프에서 한 점으로부터의 최단거리는 BFS로 구할 수 있다. 이것을 응용해서 간선의 가중치가 0 또는 1인 그래프에서 거리를 구해보자. (가중치가 0 또는 x인 경우에도 풀 수 있다.) 가중치 0의 간선으로 이어진 정점들은 모두 거리가 같다. 따라서 가중치 0의 간선을 만나면 연결된 정점들을 모두 같은 거리로 설정해주면 된다. BFS에 이를 적용하기 위해서는 queue가 아니라 deque를 이용하면 된다. 가중치 0의 간선은 먼저 처리해야 하므로 deque의 앞에 넣으면 된다. https://codeforces.com/blog/entry/22276 참고. 0-1 BFS를 이용하면 아래 문제들을 풀 수 있다. https://www..
이분 매칭 (Bipartite Matching) 이분 매칭은 이분그래프에서의 매칭을 의미한다. HopcroftKarp 알고리즘을 이용하면 $O(E\sqrt{V})$에 풀 수 있지만, 여기서는 더 쉬운 알고리즘만을 다루겠다. DFS를 활용하면 $O(VE)$로 최대 이분 매칭을 구할 수 있다. 참고. - 일반 그래프에서의 매칭은 더 어려운 문제이다. blossom 알고리즘을 이용하면 $O(V^2E)$에 된다고 한다. - weighted bipartite matching은 MCMF를 활용하여 풀 수 있다. DFS를 사용한 알고리즘은 상당히 간단하다. 이분 그래프를 $G=(L, R, E)$라 하자. $L, R$은 정점의 집합이다. $L$에 속한 정점을 차례대로 보면서 매칭을 추가해줄 것이다. $v \in L$에 대해 $v$와 연결된 정점 $u \in R$을 ..
Heavy-Light Decomposition (HLD) RMQ와 같이, 수열에서 풀 수 있는 문제들을 트리에서 풀어보자. segment tree를 이용하여 풀 수 있는 문제를 주로 다룬다. 트리를 체인 여러개로 쪼개고, 각 체인에서는 수열에서와 같이 segment tree를 이용해 답을 구한다. 그 후 여러 체인을 합쳐줄 것이다. 그러면 (원하는 구간이 걸쳐져있는 체인의 수) * (체인 1개에 대해서 구간 쿼리를 할 때 필요한 연산 수) 만큼의 연산이 필요하다. 따라서 트리에서의 구간이 적은 체인에 걸쳐지도록 하자. 이렇게 체인을 쪼개어 문제를 푸는 것이 HLD이다. HLD에서는 간선이 두 가지가 있다: Heavy edge, Light edge. Heavy edge들만 남겨놓고 Light edge를 지우면 체인들만 남게 되고, 이 체인들은 모두 조상-자식을 ..
Centroid Decomposition 트리에서 분할정복을 해보자. 그러기 위해서는 트리의 중앙을 찾은 후, 그 중앙을 기준으로 나누어진 부분들의 크기가 충분히 작도록 해야 한다. 이 '중앙'을 centroid라 한다. 구체적으로는, 트리에서 centroid를 제거하여 생기는 forest에서는 모든 트리의 크기가 원래 트리의 절반이하가 된다. 트리의 centroid는 1개 또는 2개이고, 2개일 경우에는 그 2개가 인접하다. 트리에서 centroid를 잡은 후, 그 centroid를 제거하자. 그 후 나누어진 서브트리들에서 다시 centroid를 잡자. 이 과정을 반복하면 분할정복이 가능하다. 또는 centroid를 잡은 과정을 나타내면 centroid tree가 된다. 자세한 내용은 https://koosaga.com/145 참고. 내 코드..
SOS dp (Sum over Subsets) Sum over Subsets 라는 이름답게, 부분집합의 합을 구하는 알고리즘이다. 구체적으로는, $F[mask] = \sum \limits_{i\subseteq mask} A[i]$를 구한다. $0\leq mask < 2^N$일 때 $O(N2^N)$으로 동작한다. for(int i = 0; i < (1