공대생 정리노트

그래프 G=(V,E)에서 신장 트리는 정점 집합 V를 그대로 두고 간선을 |V| - 1개만 남겨 트리가 되도록 만든 것이다. 간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소 신장 트리라고 한다. 프림 알고리즘 집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워나간다. 맨 처음 정점을 제외하고는 정점을 하나 더할 때마다 간선이 하나씩 확정된다. 배열 d[]를 각 정점을 신장 트리에 포함시키는 비용을 구하는데 사용한다. tree[v]는 정점 v를 신장 트리에 연결시키는 비용이 가장 적게 드는 간선을 저장한다. 1. 시작 정점 r의 연결 비용을 0으로, 나머지 정점들의 연결 비용을 무한대로 초기화한다. 2. 정점 r을 집합 S의 첫번째 원소로 포함시킨다. 그 후 r에 연..

분할의 균형이 맞지 않게 분할이 된 상태에서 찾고자 하는 원소가 큰 그룹에 들어가는 일이 반복되면 성능이 선형을 넘어서게 된다. 반면 일정한 상수비를 지켜서 계속 분할이 된다면 복잡도는 항상 O(n)이 된다. 즉, 99:1로 분할이 계속 되어도 최악의 경우에도 O(n)을 만족한다는 것이다. T(n) = T(99n/100) + O(n) 최악의 경우 선형 시간 선택 알고리즘 알고리즘의 대략적인 방법은 다음과 같다. 0. 전체 원소가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. 1. 전체 원소를 5개씩의 원소를 가진 그룹들로 나눈다.(이때 꼭 5개일 필요는 없다) 2. 각 그룹에서 중앙값을 찾는다. -> 상수시간 * O(n/5) = O(n) 3. 중앙값들의 중앙값을 구한다. 이때 구하는 방법은 이 알..

n개의 원소가 규칙없이 저장된 배열에서 i번째 작은 원소를 찾으려 한다. 분할 알고리즘 사용 quick sort에서 사용하는 것 처럼 기준 원소 하나를 고르고 기준 원소보다 작거나 같은 원소는 왼쪽 그룹으로, 큰 원소들은 오른쪽 그룹으로 재배치한다. 이렇게 하면 기준 원소가 전체에서 몇 번째 원소인지를 알 수 있다. 만약 기준 원소가 k번째로 작은 원소라고 해보자. i가 k보다 작다면 왼쪽 그룹에 있을 것이고, 크다면 오른쪽 그룹에 있을 것이다. 이를 재귀적으로 호출한다면 어떻게 될까? n개의 원소에서 사용되는 비용을 T(n)이라고 하자. 기준 원소가 전체 집합에서 k번째로 작은 원소라면 두 그룹은 k-1개와 n-k로 나뉜다. 그렇다면 식을 다음과 같이 쓸 수 있다. T(n) ≤ max[T(k-1), T..

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이 일..