최단 경로의 종류 단일 출발 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로를 찾는 문제 음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘 단일 도착 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제 음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘 단일 쌍 최단 경로 어떤 정점 v에서 w로 가는 최단 경로를 찾는 문제 음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘 전체 쌍 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 (플로이드-워셜 알고리즘) 다익스트라 알고리즘 음의 가중치를 갖지 않는 그래프에서 어떤 한 정..
단절점 무향 연결 그래프에서 하나의 정점과 연결된 간선들을 모두 제거했을 때 두 개의 연결 그래프로 나눠진다면 해당 정점은 단절점이다. 위의 그림에서 주황색 정점들이 단절점이다. 2번 정점을 기준으로 { 1 } 과 { 3, 4, 5, 6, 7, 8 } 으로 나뉘어진다. 4번 정점을 기준으로 { 1, 2, 3 } 과 { 5, 6, 7, 8 } 으로 나뉘어진다. 6번 정점을 기준으로 { 1, 2, 3, 4, 5, 8 } 과 { 7 } 으로 나뉘어진다. 단절점 찾기 무향 연결 그래프에서 어떤 정점 A에 연결된 정점들에 대해서 우회경로(정점 A를 거치지 않는 경로)가 없는 경우가 존재한다면 A는 단절점이다. 어떤 정점 A와 해당 정점에 연결된 정점 B에 대해서, A가 시작 정점이 아닌 경우 : \(order_A..
정렬 알고리즘 (Sorting Algorithm) 정렬 알고리즘은 크게 비교 방식(Comparisons)과 미비교 방식(Non-Comparisons)으로 나눌 수 있다. 비교 기반 정렬 알고리즘에는 거품 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬이 있다. 미비교 기반 정렬 알고리즘에는 기수 정렬과 계수 정렬이 있다. 거품 정렬 (Bubble Sort) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 수행 과정 1회전에 첫번째 원소부터 마지막 원소까지 인접한 원소끼리 대소를 비교하여 조건에 맞춰 서로 교환한다. 1회전이 끝나면 가장 큰 원소가 맨 뒤에 위치해 있으므로 2회전에는 맨 끝에 있는 원소는 정렬에서 제외한다. 이러한 방식으로 원소..
최소 공통 조상 (Lowest Common Ancestor / LCA) 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 정점 A 혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점 위의 그림에서 13번 정점과 15번 정점의 최소 공통 조상은 5번 정점이 된다. 최소 공통 조상 구하기 선형 탐색 : \(O(depth) = O(N)\) 1. 최상위 조상 정점을 시작으로 DFS 또는 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다. 2. 최소 공통 조상을 찾을 두 정점을 확인한다. 3. 먼저 두 정점의 깊이가 같아질 때까지 각각 부모를 따라 거슬러 올라간다. 4. 이때, 가리키는 정점이 다르다면 다시 각각 부모를 따라 하..
트리 무향 그래프이면서, 순환이 없는 연결 그래프 트리의 어떤 두 정점에 대해서 단순 경로가 하나 존재한다. 신장 트리 무향 연결 그래프의 부분 그래프이고, 해당 그래프의 모든 정점을 포함하는 트리 다음은 무향 연결 그래프에 대한 4가지 신장 트리이다. (E = V - 1) 깊이 우선 신장 트리와 너비 우선 신장 트리 깊이 우선 신장 트리는 무향 연결 그래프에서 DFS으로 탐색하면서 생성된 신장 트리이다. 너비 우선 신장 트리는 무향 연결 그래프에서 BFS으로 탐색하면서 생성된 신장 트리이다. 최소 신장 트리 (Minimum Spanning Tree / MST) 무향 연결 가중 그래프에서 간선의 가중치의 합이 최소인 신장 트리 그래프에서 최소 신장 트리를 만드는 알고리즘으로는, 크루스칼 알고리즘과 프림 ..
서로소 집합 교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조 - Union 연산 어떤 두 원소 a, b 에 대해서, union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산이다. \(a \in A, b \in B\) 에 대해서, union(a, b)는 \(A \cup B\) 이다. - Find 연산 어떤 원소 a에 대해서, find(a)는 a가 속한 집합(집합의 대표번호)을 반환하는 연산이다. \(a \in A\) 에 대해서, find(a)는 집합 A(집합 A의 대표번호)를 반환한다. 서로소 집합의 표현 - 초기화 - Union 연산 ex) union(1, 2) - Find 연산 ex) find(3) = 1, find(5) = 1 서로소 ..
DAG (Directed Acyclic Graph) DAG는 순환을 가지지 않는 방향 그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG 구조를 가진다. DAG에서 어떤 정점 \(v_i \in V, v_j \in V\) 에 대해서 \(v_i\) 에서 \(v_j\) 로의 경로가 존재하면, \(v_i\) 는 \(v_j\) 의 선행자이고 \(v_j\) 는 \(v_i\) 의 후행자이다. DAG에서 어떤 정점 \(v_i \in V, v_j \in V\) 에 대해서 \(v_i\) 에서 \(v_j\) 로의 간선이 존재하면, \(v_i\) 는 \(v_j\) 의 즉각 선행자이고 \(v_j\) 는 \(v_i\) 의 즉각 후행자이다. 위상정렬 DAG에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것을..
그래프 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것 정점 집합 V = { \(v_1, v_2, v_3, \ldots, v_n\) } 이고, 정점간의 연결 관계들을 나타내는 간선 집합 E = \( \{ (v_i, v_j) / v_i \in V, v_j \in V \} \subseteq V \times V \) 일 때, 그래프 G = (V, E) 이다. 그래프의 용어 무향 간선 : 정점을 연결하는 간선에 방향이 존재하지 않는다. \(\Leftrightarrow\) \( (v_i, v_j) = (v_j, v_i) \) 유향 간선 : 정점을 연결하는 간선에 방향이 존재한다. \(\Leftrightarrow\) \( (v_i, v_j) \neq (v_j, v_i) \) 인접 :..
