Algorithm

강한연결요소 : Strongly Connected Component

강한연결요소 : Strongly Connected Component Concept 방향 그래프 G의 임의의 노드 쌍 u,v에 대해 u->v, v->u로 가는 경로가 존재하면 G는 Strongly Connected 되었다고 한다 따라서 G의 u->v 로 가는 경로가 있을 때, 엣지의 방향을 정반대로 바꾼 transpose G에도 u->v로 가는 경로가 있다면 두 노드 사이에 사이클이 있어 SCC를 만족한다 Kosaraju's Algorithm #include #include #include #include #define MAX 10001 using namespace std; int n, out_len; bool check[MAX], check2[MAX]; vector r[MAX], r2[MAX]; stac..

[Algorithm: 알고리즘] 02 Prologue

목차 1. Introduction: 알고리즘 소개 - 알고리즘 - 블록체인 2. Performance Analysis: 성능 분석 - Computational complexity(계산 복잡도) - Common running times - Recurrence relation(점화식) 1) Characteristic equation(특성 다항식) 2) Repeated substitution(반복 치환) 3) Master theorem 3. Fibonacci :피보나치 수열 소개