알고리즘

강한연결요소 : 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:알고리즘] 03 Divide and Conquer

목차 0. Introduction: 분할정복 소개 - 에피소드 - DnC를 이용한 토너먼트 알고리즘 - DnC의 키 아이디어 - DnC의 추상 알고리즘 - DnC의 성능 분석 1. Recurrence Relation: 점화식 - 연습 문제 1) Characteristic equation(특성 다항식) 2) Repeated substitution(반복 치환) 3) Master theorem 2. DnC Algorithm : 분할정복 알고리즘 - 토너먼트 - 이진탐색 3. Multiplication : 곱셈 - DnC를 이용한 곱셈 알고리즘 4. Sorting : 정렬 - 병합정렬 - 퀵 정렬 5. Medians : 중앙값 - K번째로 작은 값 찾기 6. Matrix Multiplication : 행렬 곱셈

[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 :피보나치 수열 소개

[Algorithm: 알고리즘] 01 STL

목차 0. Introduction: STL 소개 - 배열/ 연결 리스트의 컨테이너, 반복자, 알고리즘 소개 - 컨테이너 - 반복자 - 알고리즘 1. Vector - 생성자 - 멤버 함수 - 연산자 2. List - 멤버 함수 3. Stack/Queue - Stack 1) 컨테이너 2) 멤버함수 - Queue 1) 컨테이너 2) 멤버 함수 3) 우선순위 큐 컨테이너 4. Set - 멤버 함수 5. Map 6. DFS - STL 을 사용하여 구현