Data Structures & Algorithms
pattern을 먼저 전처리해 두면 무작정 다시 훑는 대신 근거를 가지고 건너뛸 수 있고, graph 알고리즘과 dynamic programming은 둘 다 평범한 재귀라면 버렸을 계산을 다시 쓰면서 빨라집니다. Georgia Tech DSA IV에서 공부한 내용을 단계별로 따라가는 데모로 정리했습니다.
Module 12 · Pattern Matching
길이 n인 text 안에서 길이 m인 pattern을 찾는 문제이고, 겹쳐서 나타나는 것도 모두 셉니다. brute force는 모든 alignment를 다시 시도해 최악의 경우 O(mn)입니다. Boyer-Moore는 last occurrence table로 앞질러 건너뛰고, KMP는 failure table로 다시 맞춰 O(m + n)을 보장하며, Rabin-Karp는 rolling hash로 각 window를 걸러 낸 뒤에 문자를 비교합니다.
Module 13 · Graph Algorithms
graph는 vertex 집합과 edge 집합이고, adjacency list·adjacency matrix·edge list 중 하나로 저장됩니다. DFS와 BFS는 전부 훑는 탐색의 두 가지 템플릿이고 둘 다 O(|V| + |E|)입니다. Dijkstra 알고리즘은 queue를 priority queue로 바꿔 BFS를 weighted graph로 일반화한 것입니다.
Module 14 · MST
undirected graph의 모든 vertex를 잇는 가장 싼 트리를 만드는 두 greedy 알고리즘, Prim과 Kruskal입니다. Prim은 cut을 넘어가며 하나의 component를 바깥으로 키우고, Kruskal은 cluster를 전역적으로 합치기 때문에 cycle을 닫을 edge를 걸러 내려면 disjoint set이 필요합니다.
Module 15 · Dynamic Programming
부분 문제가 겹치는 문제를 위한 divide-and-conquer입니다. 부분 문제의 답을 다시 계산하지 않고 저장해 두면, 공간을 더 쓰는 대신 지수 시간 재귀 상당수가 다항 시간이 됩니다. LCS, 0-1 knapsack, Bellman-Ford, Floyd-Warshall 모두 이 아이디어 하나에서 나옵니다.
abacadbaabacab 안에서 abacab을 찾습니다. pattern 뒤에서부터 비교하고, 얼마나 밀지는 last occurrence table이 정합니다.
발견 위치: —
1. pattern abacab(m = 6)을 text abacadbaabacab(n = 14)에서 찾습니다. Boyer-Moore는 text를 읽기 전에 pattern부터 전처리합니다.
vertex 다섯 개짜리 graph에서 A부터 BFS를 돌리고, 초기화한 뒤 같은 시작점에서 재귀 DFS를 돌려 방문 순서가 어떻게 갈리는지 봅니다.
queue에 넣을 때 표시하기 때문에 같은 vertex가 두 번 들어가지 않습니다.
Adjacency lists: A: B, C · B: A, D · C: A, D · D: B, C, E · E: D
1. BFS는 A를 queue에 넣으면서 표시합니다. A를 dequeue하고 아직 방문하지 않은 이웃 B와 C를 넣으면서 각각 표시합니다. Queue: B, C.
A에서 시작해 MST를 바깥으로 키웁니다. 방문한 vertex와 방문하지 않은 vertex 사이의 cut을 건너는 가장 싼 edge를 매번 고르고, 중간에 dequeue됐다가 버려지는 edge도 하나 나옵니다.
1. graph는 vertex 다섯 개, undirected edge 일곱 개이고 weight가 모두 다릅니다. MST는 다섯 vertex를 모두 잇는 가장 싼 edge 네 개의 모음입니다.
"BLOG"와 "BOG"의 longest common subsequence table을 한 행씩 채운 뒤, 오른쪽 아래 칸에서부터 되짚어 올라가며 subsequence 자체를 읽어 냅니다.
lcs: —
1. 행 방향으로 x = "BLOG", 열 방향으로 y = "BOG"를 놓고 비교합니다. 0행과 0열은 전부 0입니다. 빈 prefix는 공유할 문자가 없기 때문입니다.
Boyer-Moore와 KMP는 둘 다 pattern을 미리 전처리해 두기 때문에, mismatch가 났을 때 pattern을 똑똑하게 밀어낼 수 있습니다. Rabin-Karp는 대신 rolling hash로 각 window를 걸러 내고 hash가 같을 때만 문자를 비교합니다. Boyer-Moore는 보통의 경우 O(m + n/m)으로 sublinear지만 최악에는 O(mn)까지 떨어지고, KMP는 입력과 무관하게 O(m + n)이며, Rabin-Karp는 hash가 좋으면 선형이지만 매번 collision이 나면 O(mn)입니다. alphabet이 크면 Boyer-Moore, alphabet이 작거나 text가 스트림으로 들어오면 KMP, pattern 여러 개를 한 번에 찾으면 Rabin-Karp가 맞습니다.
Module 12 · Pattern Matching
Dijkstra는 vertex를 아직 보지 않은 것, frontier(priority queue 안에 있고 최적이 아닌 경로일 수도 있는 것), 그리고 방문한 것으로 나눕니다. dequeue되는 순간 그 vertex는 확정됩니다. 더 싼 경로가 있었다면 이미 방문한 이웃을 지나 더 작은 값으로 enqueue됐을 것이기 때문입니다. 음수 edge는 정확히 그 확정 근거를 깨뜨립니다. Dijkstra는 한 번 확정한 vertex를 다시 보지 않기 때문입니다. 음수 weight에 Bellman-Ford(O(|V|·|E|))나 Floyd-Warshall(O(|V|³))이 필요한 이유가 이것입니다.
Module 13 · Graph Algorithms
Prim은 greedy입니다. 방문한 vertex 집합이 graph를 cut으로 가르고, priority queue에는 그 cut을 건너는 frontier edge들이 담기며, 그중 가장 작은 것을 dequeue하는 것이 국소적으로 최적인 선택입니다. 이 선택은 전역적으로도 맞습니다. 어떤 cut을 잡든 그 cut을 건너는 최소 비용 edge는 모든 MST에 들어가기 때문입니다. 뼈대는 Dijkstra와 같지만 넣는 우선순위가 누적 거리가 아니라 edge weight 하나뿐이고, binary heap을 쓰면 O(|E| log |E|)에 동작합니다.
Module 14 · MST
Kruskal은 edge를 weight 순으로 꺼내서 cycle을 만들지 않는 것만 남깁니다. cycle property가 그 근거입니다. edge weight가 모두 다르다면 cycle에서 가장 무거운 edge는 어떤 MST에도 들어가지 않습니다. cluster는 한 시작점에서 바깥으로 자라는 대신 전역적으로 커지기 때문에, MST가 아직 완성되지 않았는데도 모든 vertex가 이미 방문 상태일 수 있습니다. 그래서 visited set만으로는 cluster를 합치는 edge인지 cycle을 닫는 edge인지 구분하지 못합니다. disjoint set이 amortized O(α(n))의 find와 union으로 그 질문에 답해 주므로, 비용은 heap이 지배해서 O(|E| log |E|), simple graph에서는 O(|E| log |V|)가 됩니다.
Module 14 · MST
dynamic programming은 부분 문제가 반복되는 문제를 위한 divide-and-conquer입니다. 각 부분 문제를 한 번만 계산하고, 저장해 두고, 다시 씁니다. 재귀로 그대로 짠 Fibonacci는 지수 시간이지만 memoize한 쪽은 시간 O(n), 공간 O(n)입니다. 다항 공간을 내주고 다항 시간을 얻는 익숙한 교환입니다. 부분 문제를 vertex로, 의존 관계를 edge로 그려 보면 경계가 보입니다. 그 graph가 DAG일 때 DP가 통하고, top-down DP는 그 위의 DFS, bottom-up은 역방향 topological order입니다.
Module 15 · Dynamic Programming
Bellman-Ford는 모든 edge를 |V|−1번 relax합니다. shortest path가 edge를 많아야 |V|−1개 쓰기 때문입니다. Dijkstra가 다루지 못하는 음수 weight를 시간 O(|V|·|E|), 공간 O(|V|)에 처리합니다. Floyd-Warshall은 바깥 반복마다 경유할 수 있는 중간 vertex를 하나씩 늘려 가며 모든 쌍을 시간 O(|V|³), 공간 O(|V|²)에 풉니다. 그 반복이 반드시 가장 바깥에 있어야 하는 이유가 이것입니다. 둘 다 negative cycle을 잡아냅니다. Bellman-Ford는 한 라운드를 더 돌렸는데도 거리가 줄어드는 것으로, Floyd-Warshall은 대각선에 음수가 나타나는 것으로 알아냅니다.
Module 15 · Dynamic Programming
Module 12 · Pattern Matching
오른쪽에서 왼쪽으로 비교하면 window에서 가장 먼저 보는 문자가 text에서 가장 뒤에 있는 문자입니다. 그래서 거기서 mismatch가 나면 pattern을 최대 m칸까지 밀 수 있습니다. last occurrence table이 찾아보는 것이 바로 그 mismatch된 text 문자이고, pattern에 없는 문자라면 table 값이 −1이라 pattern이 그 문자를 완전히 지나쳐 이동합니다.
f[i]는 p[0..i]의 proper suffix 중 동시에 p[0..i]의 prefix이기도 한 가장 긴 것의 길이입니다. pattern index j > 0에서 mismatch가 나면 처음부터 다시 하지 않고 f[j−1]로 건너뛰기 때문에 text index가 뒤로 되돌아가는 일이 없습니다. KMP의 최악이 O(m + n)이고 최선도 linear인 이유가 이것입니다.
H(next) = (H(cur) − h(front)·b^(m−1))·b + h(new)입니다. 맨 앞 문자를 빼고, 나머지 자리를 한 칸씩 올리고, 새 문자를 뒤에 붙입니다. b^(m−1)은 초기 hash를 구할 때 한 번만 계산해 두므로 window 크기가 갱신 비용에 영향을 주지 않습니다. 다만 hash collision이 연달아 나면 탐색은 다시 O(mn)까지 떨어집니다.
Module 13 · Graph Algorithms
BFS는 queue를 쓰고, 시작점에서 edge 하나 거리인 vertex를 모두 끝낸 뒤에야 두 개 거리로 나갑니다. DFS는 재귀나 stack을 쓰고 넓게 가기 전에 깊게 내려갑니다. 둘 다 최악의 경우 O(|V| + |E|)라서, 선택은 target이 어디쯤 있는지, graph가 얼마나 깊은지, 분기가 얼마나 넓은지에서 갈립니다.
더 짧은 경로가 있었다면 이미 방문한 이웃을 지나갔어야 하고, 그런 경로는 더 작은 key로 enqueue되어 먼저 dequeue됐을 것입니다. queue에 남아 있는 frontier에는 최적이 아닌 경로가 섞여 있을 수 있지만, 최솟값을 dequeue하는 순간만큼은 확정입니다.
수업에서 쓴 구현에는 decreaseKey가 없어서 priority queue가 살펴본 edge마다 항목을 하나씩 담을 수 있습니다. 그래서 O(|E| log |E|)입니다. 이것이 log |V|로 바뀌는 경로는 둘입니다. simple graph에서는 log |E| ≤ log |V|² = 2 log |V|이므로 두 표기가 같은 bound입니다. 그리고 decreaseKey가 있으면 queue 크기가 O(|V|)를 넘지 않아 O((|V| + |E|) log |V|)가 되고, connected graph에서는 이것이 O(|E| log |V|)가 됩니다.
Module 14 · MST
dense graph는 표기상으로는 비기지만 실제로는 Prim이 낫습니다. Kruskal은 모든 edge를 dequeue하고 cycle 검사까지 하기 때문입니다. sparse graph, 이미 정렬된 edge, minimum spanning forest가 필요한 경우는 모두 Kruskal 쪽입니다. edge가 스트림으로 들어오는데 메모리가 O(|V|)뿐인 상황도 Kruskal입니다. 받을지 버릴지 판단하는 데 disjoint set만 있으면 되는 반면, Prim은 후보를 priority queue에 쌓아 둬야 하기 때문입니다.
find는 parent 포인터를 따라 대표 root까지 올라가고, path compression은 되돌아 내려오는 길에 그 경로의 모든 노드를 root에 바로 붙입니다. union by rank는 더 낮은 트리를 더 높은 root 아래에 달고 두 rank가 같을 때만 rank를 올립니다. 둘을 합치면 find와 union이 amortized O(α(n)), 즉 inverse Ackermann이라 사실상 상수입니다.
edge weight가 모두 다르면 MST는 유일하고, graph가 이미 트리인 경우도 마찬가지입니다. 음수 weight는 Dijkstra와 달리 여기서는 괜찮고, 모든 weight의 부호를 뒤집으면 같은 알고리즘이 maximum spanning tree를 찾아 줍니다.
Module 15 · Dynamic Programming
부분 문제가 겹치고 optimal substructure가 있어야 합니다. merge sort는 서로 겹치지 않는 subarray로 나누기 때문에 다시 쓸 것이 없습니다. DP는 부분 문제들이 의존 관계를 공유할 때 통하고, 그것들을 memoize하면 반복 계산이 사라집니다. 어려운 쪽은 구현이 아니라 부분 문제를 찾아내는 것입니다.
x[i]와 y[j]가 같으면 L[i][j] = L[i−1][j−1] + 1이고, 다르면 L[i][j] = max(L[i−1][j], L[i][j−1])입니다. 0행과 0열은 전부 0입니다. L[n][m]에서 backtracking하면 문자열이 복원됩니다. 대각선으로 움직일 때 그 문자를 가져가고, 위와 왼쪽 값이 같으면 어느 쪽을 골라도 됩니다. 어떤 LCS가 나오는지만 달라지고 길이는 변하지 않습니다.
capacity W는 약 log W자리로 적히기 때문에, O(nW)는 입력 크기 기준으로는 지수 시간입니다. 이것이 pseudo-polynomial time입니다. 숫자의 표현 길이가 아니라 숫자의 값에 대해 다항이라는 뜻입니다. 실행 시간이 숫자 입력에 좌우되는 알고리즘이라면 어디에나 같은 함정이 있습니다.