Algorithm/알고리즘 이론

최소 공통 조상(Lowest Common Ancestor)

최소 공통 조상(LCA)란? LCA란 트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v거나 v의 조상인 노드들 중 가장 깊은 노드이다 예를들어, 아래의 트리에서 노드 4와 3의 LCA는 1번 노드이다 다른 예로는 노드 9, 14의 LCA는 2번 노드이며, 노드 3, 13의 LCA는 3번 노드이다 여기서 한가지 사실을 알 수 있는데 노드 u,v와 이들의 LCA w의 관계이다 u,v의 최단 경로는 u-w-v 형태라는 것이다 이를 아래의 트리에서 빨간 경로로 확인할 수 있다 따라서, 트리 문제에서 최단경로를 빠르게 찾길 원한다면 가장먼저 LCA를 생각해봐야 한다 LCA 구현 방법 1. 노드 u,v 가 서로 만날때까지 부모노드를 따라서 두 노드를 옮겨 보는 방법 : 선형 탐색 두..

단절점(Articulation Point), 단절선(Articulation Bridge)

단절점(Articulation Point)이란? 하나의 컴포넌트로 구성된 무방향 그래프에서 특정 정점을 제거했을 때 두 개 이상의 컴포넌트로 나눌 수 있는 정점을 단절점이라고 한다 아래의 그래프에서 하이라이트된 정점들이 A-point이다 단절점 구하는 방법 단절점을 구하기 위해서는 먼저 단절점의 특성에 대해 알아야 한다. 어느 한 정점이 단절점이라면, 단절점에 바로 인접해 있는 정점들의 쌍은 단절점이 없으면 우회로로 인해 연결되어 있지 않아야 한다 예를 들어 5번 정점이 단절점이라고 생각해보자. 5번 정점을 제거하더라도 인접노드인 4, 6을 우회로(4-8-6)로 연결되어 있으므로 5번은 단절점이 될 수 없다 이번에는 4번 정점이 단절점이라고 생각해보자 4번 정점을 제거하게 되면 (2,3) 과 (5,8)은..

강한연결요소 : 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..

위상 정렬 Topological Sort

위상 정렬(Topological Sort)이란? 정렬 기준이 '위상'으로 여기서 위상이란 진입차수(incoming edge의 수)를 의미한다 위상 정렬의 특징 - Directed Acyclic Graph(DAG)에서만 가능 - 즉, 방향을 가지며 싸이클은 형성하지 않는 그래프를 말한다 - 보통 일의 순서를 정하는 알고리즘에서 많이 사용됨 위상 정렬 알고리즘 각 노드의 위상(incoming edge의 수)를 저장 위상이 0인 노드를 큐에 푸쉬 큐가 빌 때까지 아래 과정 반복 큐에서 노드를 꺼내 해당 노드와 연결된 노드의 간선을 모두 제거(동시에 연결된 노드의 위상을 하나씩 낮춰줌) 큐에서 꺼낸 노드를 위상정렬에 넣어줌 위상이 0인 노드를 큐에 푸쉬

[Algorithm : 알고리즘] 06 Dynamic Programming: DP

목차 0. Introduction: 동적프로그래밍 소개 1. 0/1-Knapsack 2.Weighted interval scheduling 3. Multistage Graph 4. All pairs shortest path - Floyd's algorithm

[Algorithm: 알고리즘] 05 Greedy Algorithm

목차 0. Basics: 그리디 알고리즘 기초 1. Minimum Spanning Trees : 최소 신장 트리 - 신장 트리 - 최소 비용 신장 트리 - Kruskal's Algorithm( Original ver.) : 크루스칼 알고리즘 - Kruskal's Algorithm( Improved ver.) : 크루스칼 알고리즘-성능향상 버전 - Prim's Algorithm : 프림 알고리즘 2. Knapsack Problem : 배낭 문제 3. Job sequencing with deadline : 데드라인이 있는 작업 순서 문제 - 문제 - 해결 전략 4. Optimal merge patterns : 최적 병합 패턴 - 문제 - 해결 전략 - Huffman encoding의 등장 배경 - Huffm..

[Algorithm: 알고리즘] 04 Graph

목차 0. Introduction: 그래프 소개 1. What is graph? : - 그래프의 정의 - 그래프의 종류 - 그래프의 표현 - 성능 분석 - 그래프 알고리즘의 분류 2. DFS : 무방향 그래프에서의 깊이우선탐색 - 자료구조별 탐색법 - DFS 3. DFS : 유향 그래프에서의 깊이우선탐색 - 엣지의 종류 - Directed Acyclic Graph(DAG) : 유향 비순환 그래프 4. Strongly Connected Components(SCC) : 강한연결요소 - 유향그래프에서의 연결성 - 알고리즘 5. Biconnected Components : 이중연결 요소 - Articulation point : 분절점 - Biconnected graph : 이중결합 그래프 - BCC에서 A-po..

[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 : 행렬 곱셈