이번 글에서는, 문자열 정렬과 (suffix array를 활용한) 문자열 탐색에 대해 살펴볼 것이다. 효율적인 문자열 정렬 및 탐색을 하기 위해서는, 문자열 자료형(e.g., Java: String, Python: str)의 내부 구현 방식이 숙지되어 있어야 한다. 이전 정렬 알고리즘은 $N\log N$번의 비교 연산으로 모든 유형의 자료형을 정렬한다. 하지만, 문자열을 더 빠르게 정렬하는 방법이 존재한다. (이때, 비교 연산을 사용하지 않는다.) 0. Key-indexed counting key 개수가 유한한 N개의 item을 정렬하는 알고리즘이다. Assumption 배열 index를 key로 표현하기 위해, key를 0 ~ R-1사이의 정수로 고정한다. Algorithm 각 key의 빈도수를 계산해..

이번 글에서는 mincut과 maxflow에 대해 살펴볼 것이다. Mincut problem source vertex(=s)와 target vertex(=t)를 가진 weighted digraph가 있을 때, 최소 capacity를 갖는 st-cut을 찾는 문제다. 직관적으로 말하자면, "s와 t를 최소 비용으로 분리시키는 cut"을 구하는 문제다. Definition A st-cut (cut) is a partition of the vertices into two disjoint sets, with s in one set A and t in other set B. Its capacity is the sum of the weight(=capacities) of edges from A to B. Maxfl..

이번 글에서는, weighted digraph의 대표 문제인 최소 경로 문제에 대해 살펴볼 것이다. weighted digraph가 주어졌을 때, edge v에서 edge w까지의 최소 경로를 찾는 문제다. 수많은 문제가 최단 경로 문제로 재구성될 수 있기에, 꼭 집고 가야 하는 문제다. Shortest path variants Source-sink: from one vertex to another (1-to-1) Single-source: from one vertex to every other (1-to-N) All pairs: between all pairs of vertices (N-to-N) 본문에서는, single-source 문제에 대해서만 살펴보겠다. Weighted digraph repre..

이번 글에서는, Minimum Spanning Tree에 대해 살펴볼 것이다. MST (Minimum Spanning Tree) Definition Given $G$ is undirected weighted graph with positive weights (connected). A spanning tree of $G$ is a subgraph $T$ that is both a free tree (connected and acyclic) and spanning (includes all the vertices). (spanning tree는 span하고 acyclic이기에, V-1개의 edge를 가지고 있다.) MST(Minimum Spanning Tree) of G is spanning tree whic..

이번 글에서는, 여러 가지 digraph-processing algorithm에 대해 살펴볼 것이다. Digraph Definition Digraph(=Directed Graph): set of vertices connected pairwise by directed edges (connection & direction) Terminology In-degree: number of edges leaving the vertex Out-degree: number of edges coming into the vertex Path: sequence of vertices connected by directed edges Cycle: path whose first and last vertrices are the sam..

이번 글에서는, 3가지 graph-processing algorithm(search, path, connectivity)에 대해 살펴볼 것이다. Why learning graph-processsing algorithm(s)? 그래프는 "광범위하게 사용되는 추상화(=abstraction) 모델"이다. (매우) 복잡한 구조를 가진 수 많은 객체(e.g., Internet, Seoul Metro)를 그래프로 추출(=abstract)할 수 있다. 그래프로 추상화되는 객체가 갖고 있는 problem(s)를 graph-processing problem(s)라 하며, graph-processing problem(s)의 algorithm(s)을 graph-processing algorithm(s)이라고 한다. grap..