Divide and Conquer (분할 정복) 을 배운다. merge, quick sort 를 배우고 이 과정에서 왜 combine 단계가 O(n) 이 되어야 하는지 알아본다. 뒷부분에서는 Big O 뿐만 아니라 master method, decomposition approach 를 이용해 성능을 분석한다. Divide and Conquer 각 level 의 문제 갯수는 2^j (j = 0, 1, 2…
Analysis of Algorithms, by Kevin Wayne, Robert Sedgewick in Coursera 알고리즘을 분석해야 하는 이유는 (1) Predict performance (2) Compare algorithms (3) Provide guarantees (4) Understand theoretical basis 그 중에서도 performance bug 를 피하는 것이 무엇보다 중요하다. 이를 통해 내 알고리즘이 practical large input 에 적용할 수 있을까? 고민하는 것이, 알고리즘…
Algorithm Part 1, Coursera Union Find Dynamic Connectivity N 개의 오브젝트가 있을때, Union command: connect two objects Find/connected query: is there a path connecting the two objects? 이렇게 두 경로가 연결되어있는지 아닌지를 판별하는 알고리즘은 다양하게 활용될 수 있다. Pixels in adigital photo Computers in a network Friends in a…