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

Complexity에는 Time과 Space가 있습니다. 알고리즘이 컴퓨터에서 동작하는 한, 컴퓨팅 자원을 사용하게 되고 그 중 영향력이 높은 것이 시간과 요구하는 공간이기 때문입니다. 자세한 설명은 다시 포스팅하겠습니다. Asymptotic Function Growth 두 프로그램의 Time complexity를 비교하기 위한 방법으로 사용하는 것입니다. 총 5가지 O, o, $\Omega$, $\omega$, $\Theta$가 있습니다. Upper Bound Lower Bound Tight Bound According to Input 알고리즘이나 문제의 bound를 구하는 문제는, 알고리즘이 input에 따라 어떤 성능을 보여주는지와 같게 됩니다. Upper bound는 worst case가, Low..

What is an Algorithm? 알고리즘은 문제를 해결하거나 계산을 수행하기 위한 잘 정의된, 컴퓨터 명령어로 구현가능한 유한한 시퀀스입니다. 한마디로 주어진 input 데이터를 원하는 output 데이터로 만들 수 있는 잘 정의된 계산 과정입니다. 혹은, 계산 문제(computational problem)을 해결하는 도구라고 볼 수 있습니다. Characteristics of an algorithm Input - Output - Definiteness Instruction은 clear, unambiguous하다. Finiteness 유한한 시간 내에 terminate된다. Effectiveness Unnecessary하거나 redundant step이 없다. Independence 프로그래밍 코..