Complexity Classes 세상에는 이상한 문제가 많습니다. 사람들은 그런 문제들의 난이도를 분류해서 구분하고 있습니다. P냐 NP냐 그런 것들이 다 문제의 난이도를 나타내는 말입니다. 한번 그런 문제 중 하나인 한 붓 그리기를 생각해 봅시다. 그래프에 있는 모든 edge를 한 번만 사용하는 한 붓 그리기가 가능할까요? 그래프에 있는 모든 vertex를 한번만 방문하는 한 붓 그리기가 가능할까요? 그래프에 있는 모든 vertex를 한번만 방문하되, edge의 weight의 합이 B를 넘어가지 않게 한 붓 그리기가 가능할까요? 위의 각 문제는 각각 Euler Tour, Hamiltonian Circuit, Traveling Salesman이라고 불리는 문제입니다. 통상적으로 Euler Tour 문제..

Maximum Flow Maximum Flow가 주로 사용되는 분야는 graph에서 최대 flow를 유동하고 싶은 분야이다. 대표적으로 하수도 시스템, 인터넷 네트워크, 교통량 등이 있다. Network는 directed graph G = (V, E, C)로 표현한다. C는 capacity→$R^+$이다. Flow는 f:E=(u, v) →$R$로 표현한다. f는 edge에서 항상 C보다 값이 작다. Augmented Path Elemently paht: s→t이다. 한마디로 source에서 destination까지 갈 수 있는 elemently path이다. Bottleneck은 다음과 같이 구한다. b = $min(c(v_i, v_{i+1}))$ Flow example 가능한 augmented path..

Single-Destination Shortest Path 그래프가 주어졌을 때, source에서 destination까지 shortest path를 찾는 문제이다. Optimal substructure 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 효율적으로 구해질 수 있는 경우를 말한다. 이 구조를 만족하는 경우 문제를 Greedy algorithm이나 Dynamic programming을 이용해 해결할 수 있데 된다. s→d까지의 path가 shortest라면, s→t 역시 shortest임을 의미하게 된다. 문제가 이 구조를 만족하는지 확인하는 것은 중요한 문제이다. 다음의 그래프에 대해서 Prim 알고리즘을 적용해보면 무슨 말인지 알 수 있다. Prim은 greedy하게 ed..

Graph Basics 일상의 많은 문제는 Object간의 binary 관계로 이루어져 있습니다. 고속도로나 도시의 지도가 그런 예입니다. 중요한 사실은 이런 binary 관계는 table 형태나 graph 형태로 표현이 가능하다는 것입니다. 그럼 graph 이론을 알고 있으면, 많은 문제에 적용할 수 있다 이말이야 Terminology and Representation Graph Directed graph와 Undirected graph, 두 종류로 이루어진다. Directed graph Undirected graph G = (V, E) G = (V, E) V : a set of vertices E : a binary relation on V, called edges (= a set of ordered..

Sort algorithms n개의 set이 주어졌을 때, increasing order로 key 기반 정렬을 수행하는 알고리즘이다. Time complexity와 Space complexity를 고려해야 한다. 또한 다음의 2가지 개념도 고려된다. Stability 같은 key에 대해서, key의 순서가 유지되는 정렬 In-place 추가적인 공간을 필요하지 않는 정렬 Simple sorts ; comparison based Selection sort 현재의 unsorted list에서 minimum을 선택해 정렬하는 알고리즘이다. 쉬운 알고리즘이다. $T(n)$ $S(n)$ In-place Stable $O(n^2)$ $O(n)$ x o *swap을 이용하면 in-place로 구현할 수 있다. 대신 ..

String matching Text $T$(len: n)에서 pattern $P$(len: m)를 찾는 문제입니다. Naive algorithm 쉽게 생각해보면, 모든 text 위치에서 pattern을 검사하면 string matching을 수행할 수 있습니다. 이 때의 시간 복잡도는 $O(nm)$입니다. Rabin-Karp algorithm Hash를 이용해서 문자열 매칭을 수행합니다. 구체적으로는 문자를 아스키코드 값으로 인식하고 자릿수에 따른 hash 계산을 수행하고 mod 연산한 결과를 사용합니다. 이 값이 일치하면 문자열 비교를 수행해 문자열 매칭이 이루어지는지 확인합니다. Hash 값 형성 EX) $h=t_1*10^3 + t_2*10^2 + t_3*10^1 + t_4*10^0$ 소수를 이용해..

The k th element selection n개의 숫자로 이루어진 배열에서 $k^{th}$ element를 찾는 문제입니다. 가장 쉽게 생각해보면, 배열을 정렬해서 $k^{th}$ element를 얻으면 될 것 같습니다. 보통 정렬이 $O(nlogn)$이 소요되는 데, 이보다 빠르게 linear time에 이를 수행할 수 없을까요? Randomized algorithm 가장 먼저 Divide-and-conquer 방법을 생각해 볼 수 있습니다. 다음의 방법을 생각해 봅시다. $i^{th}$ element를 pivot으로 정합니다. pivot을 기준으로 작은 값은 앞으로, 큰 값은 뒤로 옮깁니다. pivot은 배열에서 자기의 자리를 찾게 됩니다. 이렇게 해서 원하는 $k^{th}$ element를 찾..

Search algorithms Items이 주어지고 원하는 item을 찾고 싶을 때 사용하는 알고리즘입니다. Sequential search 처음부터 하나하나 비교해가며 아이템을 찾는 방법입니다. 가장 기초적인 알고리즘입니다. Best case $O(1)$ Worst case $O(n)$ Average case $O({n \over 2}) = O(n)$ Binary search 정렬된 items에 대해서 middle point부터 찾는 알고리즘입니다. Mid와 찾는 item의 대소 관계를 이용해 원하는 item을 찾습니다. Best case $O(1)$ Worst case $O(log n)$ Average case $O(log n)$ Interpolation search Best case $O(1)$ ..

한번 (1,1)에서 (4,4)까지 갈 수 있는 path를 계산해봅시다. 갈 수 있는 모든 경우의 수를 다 고려한다면, 정답을 구할 수 있을 것입니다. 하지만 이는 꾀나 비효율적인 방법입니다. 아래의 그림은 가능한 모든 경우의 수를 그래프로 나타낸 것입니다. 그래프를 보시면, 반복되는 구간이 많은 것을 알 수 있습니다. Recursion 개념을 사용해 (i,j)에서 (4,4)로 갈 수 있는 path를 생각해보면 어떨까요? 반복되는 구간을 중복해서 계산하지 않고 처리할 수 있을 것입니다. 이 방법을 Memoization이라고 합니다. Memoization을 사용할 경우, 위의 문제에 대한 Time complexity는 $O(2^{2n-1})$이 됩니다. Dynamic Programming 문제의 soluti..