Coursera 에서 제공하는 Stanford 대학교의 Algorithm Design & Analysis 수업 중 6 번째 챕터입니다. Hash Table 해시 테이블의 연산은 key 를 이용해 이런 작업들을 한다. (1) insert: add new record (2) delete: delete existing record (2) lookup: check for a particular record 가끔 사람들이 dictionary 라 부르기도 하는데, 해시테이블은 알파벳 순서같은 특정 order 로 데이터를 … Continue reading Algorithm Design & Analysis 6 – Hash Table, Universal Hashing, Bloom filters →

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 →