Coursera 에서 제공하는 Stanford 대학교의 Algorithm Design & Analysis 수업 중 5 번째 챕터입니다. Dijkstra’s Shortest-Path Algorithm BFS 는 undirected graph 에서 최단 경로를 찾지만, 이건 모든 edge 의 길이가 1일때만 그렇다. 다익스트라(dijkstra, 데이크스트라) 알고리즘은 directed graph 에서 non-negative length 에 대한 최단 경로를 찾아낼 수 있다. 각 edge 가 음수라면, 모든 수에 특정 수를 … Continue reading Algorithm Design & Analysis 5 – Dijkstra, Heap, Red-Black Tree →

Coursera 에서 제공하는 Stanford 대학교의 Algorithm Design & Analysis 수업 중 4 번째 챕터입니다. 기본적인 그래프 탐색 방법 DFS, BFS 에 대해 배우고 약간씩 응용하여 shortest path, conncected components, topological order, strongly connected components 등을 찾는 방법을 배운다. 마지막 부분에선 웹이 어떻게 생겼을까 잠깐 고민해 본다. Graph Search 그래프 탐색은 다양하게 활용할 수 있다. (1) … Continue reading Algorithm Design & Analysis 4 – Graph Search and Connectivity →

Coursera 에서 제공하는 Stanford 대학교의 Algorithm Design & Analysis 수업 중 3 번째 챕터입니다. 이번엔 지난시간에 배운 randomized algorithm 을 새로운 domain 인 그래프에 적용해 보고, contraction algorithm 이 무엇인지 알아본다. Graphs 용어 정리부터 시작하자. edge (E) 는 pair of vertices 와 같은 말이다. (E) 는 directed or undirected 일 수 있으므로 unordered pair 또는 … Continue reading Algorithm Design & Analysis 3 – Graphs, The Contraction Algorithm →

Coursera 에서 제공하는 Stanford 대학교의 Algorithm Design & Analysis 수업 중 2 번째 챕터입니다. Intuition 중복이 없는 n 개의 원소를 가진 배열에서 i 번째로 큰 원소를 얻고 싶다고 하자. 간단한 방법은 먼저 정렬을 한 뒤 거기서 i 번째 원소를 고르면 된다. 이 방법을 reduction 이라 부르는데 selection 문제를 sorting 문제로 바꾸어 푼 것이다. 이 경우 … Continue reading Algorithm Design & Analysis 2 – Randomized Selection →

Coursera 에서 제공하는 Stanford 대학교의 Algorithm Design & Analysis 수업 중 1 번째 챕터입니다. Divide and Conquer (분할 정복) 을 배운다. merge, quick sort 를 배우고 이 과정에서 왜 combine 단계가 O(n) 이 되어야 하는지 알아본다. 뒷부분에서는 Big O 뿐만 아니라 master method, decomposition approach 를 이용해 성능을 분석한다. Divide and Conquer 각 level 의 … Continue reading Algorithm Design & Analysis 1 – Divide And Conquer →