CS/알고리즘
-
String MatchingCS/알고리즘 2023. 11. 23. 15:33
String Definition : A sequence of characters $P$ : Patttern string of size $m$ Pattern Matching Problem : Given strings $T$ (text) and $P$ (pattern), find a substring of $T$ equal to $P$ Brute-Force Algorithm Compare the pattern $P$ with the text $T$ until either a match is found, or all placements of the pattern have been tried Input : text $T$ of size $n$ and pattern $P$ of size $m$ Output : s..
-
Dynamic ProgrammingCS/알고리즘 2023. 11. 22. 21:50
Dynamic Programming of a Recursive Algorithm Trade space for speed by storing solutions to sub-problems rather than re-computing them Find solutions in a dicionary(table), say soln Before any recursive call, search dictionary Before returning the solution, store it in the dictionary soln Example : fib fibDPwrap(n) Dict soln = create(n); return fibDP(soln, n); fibDP(soln, k) int fib, f1, f2; if (..
-
Graph Optimization Problems and Greedy AlgorithmsCS/알고리즘 2023. 11. 22. 20:08
Optimization Problem 최적해 (Optimal Solution) : Minimizing the total costs or Maximizing the total benefits Anaylyze all possible outcomes Make a series of choices -> Effect is to achieve the optimal Greedy Algorithms Making choices in sequence such that Each individual choice is the best Once a choice is made, it cannot be undone Possible drawback : Actions with a small short-term cost may be lea..
-
Graphs and Graph TraversalsCS/알고리즘 2023. 11. 21. 22:00
Definition 1. Directed Graph Digraph, a pair $G = (V, E)$ $V$ : Set of vertices (Node) $E$ : Set of ordered pairs of elements of $V$ 2. Undirected Graph A pair $G = (V, E)$ $V$ : Set of vertices (Node) $E$ : Set of unordered pairs of distinct elements of $V$ 3. Weighted Graph A triple $G = (V, E, W)$ $(V, E)$ is graph (directed or undirected) For an edge, $W(e)$ : weight 4. Graph Representations..
-
SortingCS/알고리즘 2023. 11. 14. 20:01
Insertion Sort 1. Strategy 원소를 적절한 순서대로 삽입(Insertion)한다. 첫 번째 원소는 정렬된 상태이다. 임의의 원소 $x$를 꺼낸다. $x$의 적절한 위치를 찾을 때까지 계속해서 배열의 원소들과 비교한다. 이를 모든 원소가 정렬될 때까지 반복한다. 2. Algorithm 입력값 : 정렬되지 않은 배열 출력값 : 오름차순으로 정렬된 배열 void insertionSort(Element[] E, int n) int xIndex; for (xIndex = 1; xIndex < n; xIndex++) Element current = E[xIndex]; Key x = current.key; int xLoc = shiftVacRec(E, xIndex, x); E[xLoc] = cur..
-
Analyzing Algorithms and Problem PrinciplesCS/알고리즘 2023. 11. 13. 21:51
Problem Solving Using Computers 컴퓨터를 사용해서 문제를 풀기 위해선 다음과 같은 절차를 거친다. Problem (문제) Strategy (문제 해결 전략) Algorithm (알고리즘) : Input (입력값), Output (결과값), Step (단계) Analysis (알고리즘 분석) : Correctness (정확도), 시간 및 공간 복잡도, Optimality (최적성) Implementation (알고리즘 구현) Verification (알고리즘 검증) Proof 어떠한 논리를 증명하기 위한 방법으로 주로 4가지를 사용한다. Counter Example (반례) Contraposition (대우) Contradiction (귀류법) Mathematical Inducti..