본문 바로가기

분류 전체보기186

[알고리즘] Greedy algorithm (1) - Optimal solution, Kruskal, Prim [1. Greedy algorithm] 1. greedy algorithm → 단계마다 한 번에 하나의 입력을 고려하되, 그 단계별로 최적의 선택을 하는 것 → 항상 최적의 결과를 도출하는 것은 아님, 다만 최적의 근사치를 도출할 수 있음 2. Minimum cost of spanning tree → 가중치그래프의 spanning tree에서 가중치의 합이 가장 적은 탐색방법 모색 → cycle 비허용 → Solution : 모든 개체들을 연결하기 → constraint : 개체가 n개 존재한다면, 최대 n-1개의 간선을 사용하기 → Feasible solution : 최대 n-1개의 간선을 사용해서 모든 개체들을 연결하기 → objective function : 사용하는 간선의 가중치 합을 최소화하기 .. 2022. 12. 9.
[알고리즘] Graph (5) - Breadth first search(BFS) [5. BFS, 너비우선탐색] 1. BFS (1) BFS 기본 전략 → vertex v를 방문할 시 → 인접한 모든 vertex를 방문한 것으로 표시 → queue에 vertex를 추가 → BFS 구현 #include #include #include #include using namespace std; vector edge[10001]; bool visit[10001]; void initVisit() { for (int i = 0; i < 10001; i++) visit[i] = 0; } void BFS(int s) { queue q; int u; q.push(s); visit[s] = 1; while (!q.empty()) { u = q.front(); q.pop(); printf("%d ", u); .. 2022. 12. 8.
[알고리즘] Graph (4) - Biconnected Components(BCC) [4. Biconnected components, 이중연결 구성요소] 1. Articulation point, 분절점 → 어느 무방향그래프의 한 vertex를 제거했을 때, 그 vertex를 제거함으로써 적어도 두 개의 connected components가 생긴다면, 그 제거된 vertex는 분절점이다. Ex) (1) vertex C 제거 => 두 개의 connected components => 따라서 C는 분절점 (2) vertex G 제거 => 두 개의 connected components => 따라서 G는 분절점 2. Biconnected graph → 분절점이 없는 무방향그래프 3. Biconnected component → Biconnected graph의 최대 서브 그래프 (각각의 서브그래프.. 2022. 12. 6.
[알고리즘] Graph (3) - Strongly connected components(SCC) [3. Strongly connected conponents] 1. 방향그래프의 연결관계 connected → 방향 그래프에서 노드 v와 노드 u가 서로에게 도달할 수 있는 경로가 존재할 때, 두 노드는 연결되어 있는 상태 2. SCC 집합 → 개체들을 상호 연결 관계에 따라 개체끼리 집합으로 분류 → SCC내의 모든 노드들은 서로 도달할 수 있음 → 위 그래프의 SCC : {A}, {B, E}, {C, F}, {D}, {G, H, I, J, K, L} 3. SCC의 성질 (1) SCC로 만든 방향그래프는 dag이다. (2) 깊이우선탐색에서 가장 높은 post number를 갖는 노드는 SCC로 만든 그래프의 source에 위치해야 한다. (3) SCC인 C와 C'가 있을 때 C에서 C'로 향하는 간선이.. 2022. 11. 29.
[알고리즘] Graph (2) - Depth-first search(DFS) [2. Depth-first search 깊이우선탐색] 1. 깊이우선탐색 - 무방향그래프 → 그래프의 탐색을 위해 Recursive call을 활용한다. → 가능한 연결되어 있는 노드들을 방문하며 → 방문 순서는 특별한 지시가 없을 경우 오름차순을 따른다. → 각 vertex v에서 탐색을 시작할 경우 → v는 이미 방문한 것으로 표시(visit[v]=1) → v에 연결된 vertex w중에서 아직 방문하지 않은(visit[w]=0인) vertex 방문 → 더이상 방문할 vertex가 없으면 직전 노드로 return Ex) 2. Spanning Tree (DFS Tree) → 주어진 그래프에서 방문되는 n-1개의 간선들로 모든 개체를 연결한 서브그래프 → DFS tree에서 root node에 다른 노드.. 2022. 11. 15.
[알고리즘] Graph (1) - Prologue [1. Prologue 개요] 1. 그래프란? → Graph : 개체와 개체들 사이의 링크로 연결된 1:1 관계를 시각적으로 나타내는 수학적 표시, 개체와 그 개체를 연결하는 링크의 집합 → vertex : 개체 → edge : 개체를 연결하는 링크, 개체간 관계를 나타냄 → G = (V, E), 그래프는 두 개의 요소(개체, 관계)를 가짐 2. 그래프의 종류 → 방항성 : 링크의 방향이 정해진 그래프 / 방향이 정해지지 않은 그래프 → 가중치 : 링크의 가중치가 정해진 그래프 / 가중치가 정해지지 않은 그래프 → 방향x, 가중치x : 무방향 그래프 → 방향x, 가중치o : 가중치 그래프 → 방향o, 가중치x : 방향그래프 → 방향o, 가중치o : 방향가중치 그래프 3. 그래프의 표현 (1) Edge l.. 2022. 11. 8.

티스토리툴바