공대생 정리노트

Minimum Cost Spaning Trees input : An undirected, connected graph G output : subgraph of G - output의 모든 edge합이 가장 작아야 한다. - 모든 vertices들은 연결이 되어 있어야 한다. 이때 첫번째 조건은 MST가 cycle이 없음을 의미한다. 만약 cycle이 존재한다면 그 cycle에서 edge를 하나 빼면 (2)의 조건을 만족하면서 더 작은 subgraph가 생기기 때문이다. output은 여러개일 수 있으나 cost는 어떠한 solution에 대해서도 같다. Prim's MST Algorithm 아무 vertex N에서 시작한다. MST에 N을 추가한다. N과 연결된 edge들 중 가장 작은 edge인 (N,M..

Shortest Paths Problems Input : A graph with weights Output : shortest path 어떻게 해야 shortest path를 계산할 수 있을까? Definitions δ(s, u) -> vertex s에서 u까지의 가장 짧은 거리 w(u, v) -> u에서 v를 연결하는 edge의 weight. 그러한 edge가 없다면 무한대로 정의된다. Algorithm by Dijkstra vertex s에서 출발하여 다른 모든 vertices들을 방문하는 shortest path를 찾아보자. visited vertices들을 가지고 있는 set S를 만든다. 그리고 size n인 array D도 만든다. array D에는 s로부터의 현재 estimate된 거리를 담..

Graph Traversals Depth First Search (DFS) 어떠한 vertex s를 방문하면 그 s의 neighbor vertex v를 방문하고, 그 v의 neighbor vertex v'을 방문하는 것을 반복. 모든 vertex를 방문할 때까지 반복한다. stack을 이용하면 쉽게 구현할 수 있다. cost : O(|V| + |E|) Breath First Search (BFS) DFS와 비슷하지만 stack이 아니라 queue를 이용한다. 어떠한 vertex를 방문하면 그 vertex의 neighbors들을 모두 방문 후 tree에서 깊어진다. Cost : O(|V| + |E|) Topological Sort 위에 나온 것처럼 전제조건이 있을 때(J2는 J1보다 먼저 나오면 안되고, ..

Graph Graph G = (V,E)라고 표기하고 vertices(node)의 집합 V와 edges의 집합 E로 구성되어 있다. vertices의 수는 |V|, edges의 수는 |E|라고 표시한다. Path edge들로 연결된 vertice들의 배열을 말한다. 예를 들어 위의 graph에서 0,4,1,3,2,4는 path이다. path 중에서도 path에 있는 모든 vertice들이 서로 다르다면 그 path는 simple하다고 한다. 예를 들어 0,4,1,3,2는 simple path이다. Cycle 길이가 3이상인 path가 한 vertice에서 나와 자기 자신에게 연결된 것을 cycle이라고 한다. 예를 들어 위의 graph에서 1,3,2,4,1,3,2,4,1은 cycle이다. cycle중에서 ..

Collision Resolution Collision resolution에는 Open hashing과 Closed hashing이 있다. Open hashing Collision이 생기면 table 밖에 저장한다. 한계점으로는 사용이 안되는 slot이 생길 수 있다. Closed Hashing Collision이 생기면 table안에 있는 다른 slot에 저장한다. 다음의 예들은 Closed Hashing의 종류들중 하나이다. Bucket Hashing Hash table slot들을 bucket으로 나눈다. 왼쪽의 table의 한 예이다. 10개의 칸이 있지만 bucket은 5개이다. h(k) = k mod 5이다. 같은 hash 값이 나와도 bucket안에 공간이 있기 때문에 collision이 일..

Hashing 어떠한 key값이 주어지면 그 key 값으로 상수시간에 원하는 값을 찾을 수 있게 하는 것이 Hashing이다. record 값을 담고 있는 Hash table을 이용하는데, 이 Hash table을 편의상 HT라고 하자. HT가 가지고 있는 slot의 개수를 M개라고 하자. 우리는 key 값을 mapping하는 Hash function을 이용한다. 이 hash function을 h라고 하자. 어느 key 값 K가 주어졌을 때 h(K)의 범위는 다음과 같다. 0 1) key가 짝수만 들어온다면 홀수 slot들은 쓰이지 않는다 2) K가 큰 값이면 모든 bit를 사용하지 않고 마지막 bit 4개만 사용한다. 이러한 이유로 좋은 hash function이 아니다. 1) 해결 방법 : M을 소수..

Heuristics self-organizing lists는 패턴에 기반하여 record를 정렬한다. 이때 어떻게 정렬할지에 대하여 Heuristic을 사용하게 된다. 자주 사용하는 item을 앞으로 오게 하는 것이 idea이다. Heuristics 예 처음에 ABCDEFGH로 정렬된 record를 가지고 있다고 생각해보자. Access pattern은 F D F G E G F A D F G E 순으로 왔다고 가정하자. 1. Count Heuristic historical frequency에 기반하여 정렬한다. 2. Move-to-front Heuristics 최근 access한 record를 제일 앞에 정렬한다. 3. Transpose Heuristic 맨 앞으로 옮기는 것이 아닌 바로 앞에 있는 re..

Jump Search Ordered Array에 대하여 search를 할 때 k의 배수번째 element만 check를 한다. 만약 check한 element가 찾고자 하는 원소의 value보다 작다면 계속 진행한다. 그렇지 않다면 그 전 원소들에 대하여 linear search를 진행한다. Analysis of Jump Search input size가 n이라고 하자. 만약 (m-1)k