Hash Table 해시 테이블의 연산은 key 를 이용해 이런 작업들을 한다. (1) insert: add new record (2) delete: delete existing record (2) lookup: check for a particular record 가끔 사람들이 dictionary 라 부르기도 하는데, 해시테이블은 알파벳 순서같은 특정 order 로 데이터를 저장하진 않는다. 이 3가지 연산이 거의 O(1) 라…
Dijkstra's Shortest-Path Algorithm BFS 는 undirected graph 에서 최단 경로를 찾지만, 이건 모든 edge 의 길이가 1일때만 그렇다. 다익스트라(dijkstra, 데이크스트라) 알고리즘은 directed graph 에서 non-negative length 에 대한 최단 경로를 찾아낼 수 있다. 각 edge 가 음수라면, 모든 수에 특정 수를 더해 양수로 만들어도, 아니면 음수 그 자체로 다익스트라…
기본적인 그래프 탐색 방법 DFS, BFS 에 대해 배우고 약간씩 응용하여 shortest path, conncected components, topological order, strongly connected components 등을 찾는 방법을 배운다. 마지막 부분에선 웹이 어떻게 생겼을까 잠깐 고민해 본다. Graph Search 그래프 탐색은 다양하게 활용할 수 있다. (1) check if a network is connected (2) driving directoin…
이번엔 지난시간에 배운 randomized algorithm 을 새로운 domain 인 그래프에 적용해 보고, contraction algorithm 이 무엇인지 알아본다. Graphs 용어 정리부터 시작하자. edge (E) 는 pair of vertices 와 같은 말이다. (E) 는 directed or undirected 일 수 있으므로 unordered pair 또는 ordered pair 일 수 있다. directed edges 는 다른말로…
Intuition 중복이 없는 n 개의 원소를 가진 배열에서 i 번째로 큰 원소를 얻고 싶다고 하자. 간단한 방법은 먼저 정렬을 한 뒤 거기서 i 번째 원소를 고르면 된다. 이 방법을 reduction 이라 부르는데 selection 문제를 sorting 문제로 바꾸어 푼 것이다. 이 경우 정렬에 머지소트를 사용한다면 O(n logn) 만큼의 시간이 걸릴…