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 프로그래밍 코..