Algorithm/Algorithm (이론)

0. 사전 지식 Undirected Graph DFS Traversal makes Forest// Undirected Graph는 시작점이 어디든 Tree 개수 일치 Directed Graph는 시작점 따라 Tree 개수가 다름. 1. 정의 Strongly Connected => 모든 쌍에서 길이 다 있음. 2. 특성 가질 수 있는 Edge 3종류 Cross, Back, Forward Edge Leaf Node에서 좌-> 우 Cross Edge가 불가능 한 이유는 DFS Traversal알고리즘 상 더이상 인접 노드가 없을 때 까지 깊이 들어가는데 좌->우 Cross Edge 존재 시 우측 노드를 이미 추가했었어야 한다. ∴ DFS Traversal Algorithm에 모순. 3. 알고리즘 1. DFS ..

1. 개념 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환..

1. 소수란? 1과 자기 자신이외 어떠한 약수도 가지지 않는 자연수 2부터 N/2 까지 나누어 떨어지는 수가 없으면 N은 소수이다. p : 몫 q: 나머지 N = ap + q (0

Disjoint Set 서로 중복되지 않는 부분집합만으로 이뤄진 자료구조 = 서로소 집합 자료구조 Union-Find Disjoint Set을 표현할 때 사용하는 알고리즘. 2가지 자료구조로 구현할 수 있다. (Array, Tree) When to use? (1) Detect cycle in a undirected graph (2) Check relationship between sets (3) Kruskal Algrotihm * condition : The graph doesn't contain any self-loops Key For each edge, make subsets using both the vertices of the edge If both the vertices are in the sa..

Greatest Common Divisor Problem 임의의 자연수 n, m (단, n > m) 에 대한 최대공약수? Input 자연수 n, m Output Largest D s.t n % D and m % D == 0 s.t: Search That의 약자. [1] n-gcd 가장 생각하기 쉬운 알고리즘. n - gcd (n,m) D 정확성 분석 -> 성능 분석의 절차를 거친다.