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..

Greedy Algorithm 우리가 결정을 내릴 때, 현 상태에서 제일 좋은 결과(=locally best)를 선택하는 알고리즘입니다. 많은 경우에 Global optimal solution이 아니기 때문에 사용이 제한적이지만, Greedy algorithm으로 global optimal solution이 나오는 경우나 여러 제약으로 인해 optimal solution을 찾는 것이 불가능한 경우에 사용되는 알고리즘입니다. Returning changes 우리에게 k 코인이 있을 때, 최대한 적은 수의 코인으로 교환해 준다고 생각해 봅시다. [quarter(25c), dime(10c), nickel(5c), penny(1c)] 총 6개의 코인으로 교환해줄 수 있습니다. 항상 optimal solution..

들어가기에 앞서서 stack의 time complexity를 분석해 봅시다. 3가지 operation이 있고 각각의 시간 복잡도는 다음과 같이 소요됩니다. Push Pop Multipop(k) O(1) O(1) O(min(k,s)) = O(n) worst case Worst-case analysis $n×O(n) = O(n^2)$ Probabilistic analysis 각각의 operation이 차지하는 비율이 ${n \over 3}$이라고 생각해 볼 수 있습니다. 따라서 시간 복잡도는 다음과 같습니다. $T(A) = {n \over 3}O(1) + {n \over 3}O(1) + {n \over 3}O(n) = O(n^2)$ Amortized Analysis 기존처럼 하나의 operation이 아니라..

알고리즘의 성능을 평가할 때, Time complexity를 분석하며, 이 값은 Input 데이터에 의해 바뀔 수 있다고 학습했습니다. Upper bound, Lower bound, Tight bound를 구하는 노력이 알고리즘의 Best case, Worst case, Average case와 관련이 있게 되는 이유이고요. 우리가 알고리즘을 평가할 때, Best case는 별로 관심이 없습니다. 실질적으로 사용하기 위해서는 Worst case와 Average case가 중요하기 때문입니다. Worst case에 대한 시간 복잡도는 비교적 쉽게 구할 수 있습니다. 알고리즘의 수도 코드를 보면서, 최악의 경우를 가정하고 instruction을 따라가면 되기 때문입니다. 반면 Average case는 가능한..

만약 어떤 문제가 작은 문제들로 나누어질 수 있다면, 이 문제는 recurrence relation으로 해결할 수 있습니다. 이 방법을 'Divide-and-conquer'라고 합니다. Recurrence Relation 다음의 특징을 가지고 있습니다. $a_n$이 $a_i$, $a_j$.. 등과 같이 표현되는 경우 (i, j < n) Boundary condition 계산이 시작될 수 있게 해주는 하나 이상의 값들 Example $a_0$ = 1, $a_1$ = 1 $a_n$ = $a_{n-1}$ + $a_{n-2}$ 대표적인 예시로는 Factorial, Fibonacci number가 있습니다. Example : Factorial 팩토리얼은 다음과 같이 정의됩니다. $n! = n*(n-1)*(n-2)..