어제의 나보다 성장한 오늘의 나

Red - Black Tree Binary search tree 중 하나인 AVL Tree 이다. Binary search tree -> 왼쪽 서브트리에는 루트 보다 작은 값이 , 오른쪽 서브트리에는 루트 보다 큰 값이 들어간다. AVL tree -> height가 2이상 차이나지 않는다. Red - Black tree는 이 두 가지 특징을 모두 가진다. Red - Black tree의 5 가지 특징 1) 모든 노드가 red or black 이다. 2) 모든 Leaf 노드는 black 이다. 3) 만약 노드가 red 이라면 Child 노드들은 black 이다. 4) 모든 노드 -> 자식 노드 중 Leaf 노드 경로의 black의 갯수가 같다. 5) 루트는 항상 black 위 다섯 가지 조건을 만족하면 R..

문자열 매칭 문제를 해결하는 Knuth-Morris-Pratt Algorithm 에 대해서 공부해보자. 문자열 매칭 문제란? 문자열에 주어진 패턴(특정 문자열)이 몇번 나타나는 지 찾는 문제 Knuth-Morris-Pratt Algorithm 소개 Text T = "bacbababaabcbab" Pattern P = "ababaca" 문자열 T에서 패턴 P를 찾는 과정에서 처음 index부터 차례로 비교하다가 이렇게 일부가 매칭 되다가 틀렸다면..! 일반 적인 매칭 방법에서는 패턴이 시작한 부분(ababa 의 맨 앞 a) 의 그 다음 부분 (ababa 의 앞에 있는 b) 에서 다시 매칭을 시작해야 한다. 이 것보다 더 효율 적으로 하는 방법은 없을까? 그러니까 어차피 b 부터 시작하면 패턴이 a 부터 시..

i-th order statistic 란?? i 번째로 작은 원소를 뜻한다. The Selection Problem 란?? i 번째 작은 원소를 찾는 것이다. 오늘은 세 가지 Selection Problem Algorithm에 대해서 배워 볼 것이다. Selection Problem Algorithm 3 가지 1) Naive Algorithm 2) Randomized Selection 3) Worst-Case Linear-Time Selection 1) Naive Algorithm 정렬 후 i 번째 작은 값을 고르는 방법 시간 복잡도 Θ(n lgn) merge sort + Pick i-th smallest element = Θ(n lgn) + Θ(1) = Θ(n lgn) 간단하지만 오래 걸린다. 2) R..

String matching problem 특정 Text에서 주어진 Pattern이 나타나는 모든 index를 구한다. 이 때의 index를 valid shift 라고 부른다. Valid shift Example 위 그림에서 Pattern P가 text T에서 index 3에서 나타난다. (s = 3 부분) 이 때 3은 valid shift 가 된다. (Index 0 , 1 , 2는 각각 abca , bcab , caba로 pattern이 나타나지 않는다. 그래서 Index 0 , 1, 2는 invalid shift) s = valid shift 일때 Text[s + i] = Pattern[i] 만족 valid shift를 모두 구하는 알고리즘 두 가지 1) Naïve - String - Matching..

오늘은 Radix sort 에 대해서 알아보려고 한다. Radix sort란? 낮은 자리 수부터 정렬하여 숫자들을 빠르게 정렬할 수 있는 sort 방식이다. 장점 ◎ Stable sort ◎ θ(n) 까지 가능 ◎ LSD sort 배경 지식 LSD , MSD LSD : Least Significant Digit 의 약자로 낮은 자릿수를 뜻한다. MSD : Most Significant Digit 의 약자로 높은 자릿수를 뜻한다. 52,314 를 예로 들면 가장 중요한 숫자는 10,000의 자리에 있는 5 이다. 그리고 가장 덜 중요한 숫자는 1의 자리에 있는 4이다. 즉 , LSD sort는 낮은 자리 부터 정렬을 하겠다는 것이고, MSD sort는 높은 자리 부터 정렬을 하겠다는 것이다. Radix s..

오늘은 counting sort( 계수 정렬 )에 대해서 알아보려고 한다. Counting sort는 다른 sort들에 비해 조건들이 추가적으로 더 있다. 그럼에도 불구하고 사용하는 이유는 조건들을 충족시키면 무려 θ(n)까지 가능 하다. 특징 ◎ Stable sort ◎ Not Sort-In-Place ※ stable sort : 중복된 값을 가지는 원소들끼리의 순서가 sort 전/후로 바뀌지 않는 sorting ※ Sort-In-Place : 추가적인 메모리(추가 array) 없이 원소들이 담겨 있는 array에서 sorting 이 일어남 시간 복잡도 θ( n + k ) n : 원소의 개수 k : 원소 들의 값의 범위 ( 만약 원소의 최대 값이 6 이라면 k는 6이고 원소들은 0~6 사이의 값을 가진..

오늘은 Minimum spanning tree(MST)에 대해 알아보고 Graph에서 MST를 찾아내는 알고리즘 두 가지 (kruskal's algorithm , Prim's algorithm)에 대해서 알아 보자. MST란? Minimum : edge들의 weight의 총합이 가장 작다. Spanning : 모든 vertex들을 포함 한다. Tree : Cycle 이 없고 edge의 갯수가 vertex의 갯수-1 개 인 그래프. 이 세 가지 조건을 가진 것이 MST이다. 참고로 MST는 undirected graph에서만 정의 된다. 예를 들어 위와 같은 그래프가 있다고 했을 때 이 것의 MST는 아래와 같다. 확인해보자 edge들의 weight 총 합이 가장 작고, 모든 vertex들을 포함 하고, ..

이번 포스팅에서는 자료 구조 Graph를 이용 하여 Shortest Path를 찾는 방법에 대해서 알아 보려고 한다. Shortest Path 의 특성들 ◎ shorest path는 shorest subpaths 들로 구성되어 있다. (optimal substructure) ◎ cycle을 포함 하지 않는다. 크게 Single-source shortest path 와 All-pairs shortest-paths 로 나누었다. single-source shortest path : 주어진 source vertex에서 Graph 내의 모든 vertex 까지의 가장 가까운 거리 All-pairs shortest-paths : 모든 vertex u에 대하여 u 에서 v로 가는 shortest path Single..