학교 수업/알고리즘
-
알고리즘 ch13 NP-complete Problems학교 수업/알고리즘 2020. 6. 16. 17:56
Optimization problem : 최적의 답를 찾는 문제 ex) shortest pathDecision problem : 답이 yes or no 인 문제 Class P - 어떤 decision 문제에 대해 polynomial time에 그 문제에 대한 해결법을 찾아낼 수 있다면, 그 문제는 클래스 P에 속한다. 즉, 다항시간내에 풀 수 있는 decision 문제들의 class를 class P라고 한다. 다항시간(polynomial time) : O(n^k) 다항시간내에 풀 수 있는 문제들은 tractable하다고 한다.문제의 어떤 알고리즘이 다항시간내에 풀린다면 efficient 알고리즘이라고 한다. Class NP- 어떤 문제가 non-deterministic polynomial time alg..
-
알고리즘 ch11 String match학교 수업/알고리즘 2020. 6. 16. 15:21
String- 문자의 나열- Substring : 연속되는 부분 문자열, Subsequence : 연속되지않는 부분 문자열 예시로 ACDEF와 ABKEF가 있다고 하자.substring = EF ACDEF ABKEF subsequence = AEF ACDEF ABKEF- Prefix : 문자열의 첫번째 문자부터 시작되는 부분문자열, Suffix : 문자열의 마지막문자부터 거꾸로 보는 부분문자열예시로 문자열 ALGORITHM이 있다고 하자prefix = AALALGALGO...ALGORITHMsuffix = MHMTHMITHM...ALGORITHM 본인 자기자신의 문자열을 제외하면 proper prefix, proper suffix라고 한다.예시로 설명하자면 ALGORITHM 을 제외한 것 String m..
-
알고리즘 ch10 Dynamic Programming학교 수업/알고리즘 2020. 6. 15. 19:29
Dynamic Programming- 큰 문제를 작은 문제로 나눠서 푸는 문제- Optimization problem 푸는 방법 중 하나이다. * divide and conquer과 다른점 : 메모리를 이용해 중복 계산을 하지 않는다. - 풀이 과정 ① 문제 특성을 파악 ② 점화식 정의 ③ 점화식대로 계산 수행 - 두가지 방식으로 나뉨 1) Top-down 방식 : recursion -> memoization 2) Bottom-up 방식 : Loop - dp로 풀수있는 optimization problem 예시) Matrix-Chain Multiplication problem : 두 개 이상의 행렬의 순서가 주어질 때 행렬의 곱셈에서 곱셈 연산의 수를 최소화하는 방법을 찾는 것 행렬의 곱 ABCD 에 대..
-
알고리즘 ch8 Greedy algotithm학교 수업/알고리즘 2020. 6. 15. 18:50
Optimization Problem- 여러개의 가능한 답 중에 가장 최적의 답 또는 최적의 답과 가까운 답을 고르는 문제- 비용을 최소화 한다거나 이익을 최대화 하는 답을 고르는 문제 Greedy Algorithm- 최적해를 구하는 데에 사용되는 근사적인 방법. - 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. (미래를 생각하지 않고 각 단계에서 최선의 선택을 함) Optimization problem 중 greedy 방법을 사용하는 문제1. Minimum Spanning Tree (MST) - Spanning tree 중 사용된 간선들의 가중치 합이 최소인 트리 즉, 그래프 내에 있는 모든 정점들을 가장 적은 수..
-
알고리즘 ch6 (2) Red-black tree학교 수업/알고리즘 2020. 6. 14. 20:48
Binary Search Tree- Binary Tree + Binary invariant(왼쪽 subtree는 더 작은 값 , 오른쪽 subtree는 더 큰 값)- 각각의 노드들의 key는 unique하며, 완쪽자식의 key는 부모보다 작으며 오른쪽 자식의 key는 부모보다 큰 값이다.- complexity 평균 최악 Insert O(logn) O(n) Remove O(logn) O(n) Search O(logn) O(n) 사슬모양처럼 긴 모양을 경우 최악의 경우고, balanced 모양일 경우 평균의 경우다. - 중회순회(inorder traversal) 시에 오름차순으로 정렬된 key값을 얻을수 있다. Red Black Tree- Binary search Tree 이면서 Balanced Tree이다..
-
알고리즘 ch 6 array doubling학교 수업/알고리즘 2020. 6. 14. 20:02
Dynamic Sets and Searching Array Doubling - 배열의 크기를 늘려야 할 때 원래 배열의 2배 크기를 할당 받아 원래의 배열에 있던 값들을 옮기는 작업. - 값을 하나 옮길 때 t시간이 덜린다고 하면, size n의 배열에 n+1번째 값이 들어올 때 2n개의 새로운 메모리를 할당 받아 n개의 값들을 옮기고 n+1번째의 원소를 입력해야 한다. 이 작업에는 기존 n개의 원소를 옮길 때 t*n의 시간이 필요할 것이다. 그럼 이 작업을 포함해 이전의 총 이동 시간을 생각해보면 t*n + t*n/2 + t*n/4 + ... = t(n + n/2 + n/4 + 1) 의 시간이 걸렸을 것이며 이는 총 2t*n보다는 적게 걸렸을 것이다. Array doubling이 중요한 이유는 1개의 ..
-
알고리즘 ch7 Graph학교 수업/알고리즘 2020. 6. 13. 23:44
Graph and Graph Traversals Graph- 정점과 간선으로 이루어지며 트리와 달리 계층(부모-자식)이 존재하지 않는 자료구조- 주로 G(V,E)로 표현한다. (V:정점, E:간선)- Directed graph : 간선이 방향이 있는 그래프, Digraph라고도 한다. 정점이 v와 w가 있고, v에서 w로 가는 간선이 있다면 directed edge는 (v,w)로 표현한다. 혹은 v→w , 간단하게 vw라고도 한다.v는 source 또는 start라고 부르고, w는 destination 또는 end라고 부른다.(v,w) ≠ (w,v) : 방향간선이므로 둘은 다르다- Undirected Graph : 간선이 방향이 없는 그래프undirected graph는 자기 자신으로 가는 간선을 정의하..
-
알고리즘 ch 1~2학교 수업/알고리즘 2020. 6. 13. 20:15
알고리즘 - Computer Algorithm 알고리즘이란? 컴퓨터를 이용하여 문제를 해결하는 순서적인 절차를 만들어 놓은 것. - 컴퓨터를 이용하여 문제를 해결하는 6단계1) Problem: 문제 파악, 문제의 input과 output확인2) Strategy: 전략 구성3) Algorithm: 알고리즘 설계Input, output에 따라 step별로 어떻게 할 것인지 설계4) Analysis: 알고리즘 분석 기준: correctness(정확성), time&space(효율성), optimality(최적화된 방법인가)5) Implementation: 수행6) Verification: 확인 - Analysis of the Algorithm 알고리즘 분석방법1. 실험적 방식 : 실제 해당 알고리즘을 기계에서 ..