본문 바로가기

알고리즘18

NP-Complete Problems Optimization Problem vs Decision Problem - Optimization Problem - Find a feasible solution with the best value - SHORTEST-PATH 가장 적은 edge로 가는 경로 찾기 - Decision Problem - 답이 yes or no - PATH: given a graph G and vertices u and v, and an integer k, is there a path from u to consisting of at most k edges? k 이하로 가는 경로가 존재하는가? Polynomial Time: Class P - 어떤 상수 k에 대해 T(n)=O(nk) 라면 그 알고리즘은 Polynomial tim.. 2021. 6. 29.
String Matching Pattern matching algorithms (=string matching algorithm) - Brute-force (=Naive) - Knuth-Morris-Pratt (KMP) - Boyer-Moore (BM) * KMP와 Boyer는 pattern을 전처리(preprocessing)한다. - text: 긴 문자열, pattern: 짧은 문자열 Strings - string은 0개 이상 char의 나열. 0개면 empty string - P를 길이 m인 string이라 하면, - substring P[i..j]: i와 j 사이의 임의의 연속된 char들의 나열 - prefix (접두사): P[0..i]인 substring - suffix (접미사): P[i...m-1]인 substring .. 2021. 6. 28.
Dynamic Programming Dynamic Programming Version of a Recursive Algorithm - 시간 절약을 위해 메모리를 더 사용. sub-problem을 저장함으로써 중복된 계산을 피함. - 재귀 호출하기 전에, subproblem Q에 대한 solution이 dictionary soln에 이미 있는지 확인한다. 없으면 재귀 호출하고, 결과를 저장한다. - ex) 피보나치 Matrix-Chain Multiplication problem - matrix chain ( )의 곱셈 연산의 수가 최소가 되는 순서 구하기(행렬곱은 순서에 따라 연산의 수가 달라지니까) -> 최적화 문제! - Computation Time - p x q 와 q x r 두 행렬을 곱한다면 - pqr scalar multiplic.. 2021. 6. 28.
Transitive Closure, All-pairs Shortest Paths - single pair shortest는 다익스트라, all-pairs shortest는 Floyd-Warshall Transitive Closure - digraph G의 transitive closure G’는 - G의 정점을 모두 가짐d - G에 u->v인 경로가 있다면(직접연결이 아니어도), G’는 u->인 directed edge를 가짐 (G에 a->b>c 경로가 있다면, G’에 a->c를 추가한다.) - n번의 DFS로도 (O(n(n+m))->O(n3)) 가능하지만, 대신 dynamic programming:Floyd-Warshall ! Floyd-Warshall Algorithm으로 transitive closure 만들기 - n*n 배열을 만들고, 연결된 정점은 1로 채움 - 세로로 순서.. 2021. 6. 28.
Graph optimization Problems and Greedy Algorithms Optimimzation Problems - 최소/최대 total cost 계산 - 모든 가능한 outcome을 계산해 최선의 것을 찾는다. Greedy Algorithms - “short term” criterion에 따라, 각각의 선택이 최선이 되게 함. - 한번 결정되면 취소할 수 없음. 나중 가서 그게 나쁜 선택이었을지라도 어쩔 수 없음. Graph Optimization Problems - 몇몇 optimization 문제들은 greedy algorithm으로 해결할 수 있다. - Minimum cost for connectiong all vertices - Minumum spanning tree 알고리즘 -> Prim, Kruskal - Shortest Path between two verti.. 2021. 6. 28.
Graphs and Graph Traversals Directed graph (digraph) - G = (V, E) - V: vertex들의 집합 - E: V 원소들의 순서쌍 집합 - directed edge (v, w)는 v->w 또는 vw로 나타냄. Undirected graph - G = (V, E) - V: vertex들의 집합 - E: V 원소들의 순서가 없는 쌍 집합 - undirected edge {v, w}는 v-w 또는 vw, wv로 나타냄. - incident: 간선-정점 간의 연결 관계 / adjacent: 정점-정점 간의 인접 관계 Weighted Graph - edge에 값이 있는 경우. - (V, E, W)또는 (V, E)로 나타냄 Graph Representations - G = (V, E), n = |V|, m = |E|,.. 2021. 6. 28.

티스토리툴바