복습노트 복습노트

Ford-Fullkerson 알고리즘을 통해 maximum bipartite matching을 찾는데 시간 복잡도는 O(VE)가 걸렸다. 우리는 Hopcroft-Karp 알고리즘을 통해 O(√V * E)의 시간복잡도를 알아볼것이다. 2~5 번째 줄은 O(√V) 만큼 반복 3번째 줄은 O(E) 만큼 반복 먼저 maximal set of vertex-disjoint shortest M-augmenting path를 찾는 방법을 볼것이다. phase 1 : undirected 그래프인 G를 directed 버전인 GM을 형성한다. phase 2 : bfs을 통해 GM에서 directed 비순환 그래프 H를 생성한다. phase 3 : H의 전치 HT에서 dfs를 실행함으로써 maximal set of vert..

Graph G = (V, E)라고 표현 V = 정점, E = 간선 |V| = V집합의 갯수 |E| = E집합의 갯수 예를 들어 V = {1, 2, 3, 4, 5}일 때 |V| = 5 이다. n개의 정점이 있는 그래프에서 최대 간선은 n(n-1) / 2 개이다. 만약 그래프가 n개의 정점이있고 간선은 n(n-1)/2 개 있으면 완전 그래프라고 부른다. 그래프의 표현은 2가지가 있다. 1. Adjacency List 2. Adjacency Matrix Adjacency List 공간 복잡도는 O(V + E) 이다. Adjacency Matrix |V| * |V| 크기의 배열을 생성 공간 복잡도는 O(V^2) Depth First Search (DFS) 한 정점을 계속 깊이 탐색하는 알고리즘 이다. 모든 정점..

An Activity-Selection Problem activity들의 시작 시간은 s이고 끝나는 시간은 f이다. 여기서 최대 몇개의 activity들을 할 수 있을지 구하는 것이다. 예를 들어 3번째 activity는 0분에 시작해 6분에 끝난다. {3, 9, 11}을 선택하면 {0~6}, {8~11}, {12~16}의 시간들을 즐길 수 있다. 즉, 시간이 겹치지 않으면서 최대로 많은 activity를 하는 것이 목표이다. 그리디 알고리즘을 활용해 최적의 결과만을 선택하면 결국 최적의 결과를 얻을 수 있다. 최적의 경우는 구할 수 있지만, 모든 최적의 경우는 다 구할 수 없다. 그렇다면 그리디 선택을 어떻게 할것인가? 현재 시간을 기준으로 할 수 있는 끝나는 시간이 가장 빠른 활동만을 계속하는 것이다..

Asymtotic Notation(점근적 표기법) 세타 표기법 평균 ex:7n^3 n^3 오메가 표기법 최소 시간 (가장 최선의 시간) ex: 7n ^ 3 n ^3, n ^2, n^1 모두 true 빅오 표기법 최대 시간 (가장 최악의 시간) ex:7n^3 n^3, n^4, n^5 모두 true

Insertion sort INSERTION-Sort(A, n) for i = 2 to n key = A[i] //Insert A[i] into the sorted subarray A[1 : i-1]. j = i - 1 while j>0 and A[j] > key A[j+1] = A[j] j = j-1 A[j+1] = key A[1 : i-1] 까지는 loop invariant(루프 불변성) 이 성립됩니다. 적은 수의 원소를 정렬할 때는 효율적임 Merge Sort Merge(A, p, q, r) n_l = q - p + 1 //중간점 p를 중심으로 왼쪽 n_r = r - q // 중간점 p + 1부터 q까지 오른쪽 새 배열 L[0..n_l - 1] and R[0 : n_r-1] for i = 0 to ..