✏️ 알고리즘/그래프 알고리즘

[18강] 최소 신장 트리 (MST)

안녕하세요 Gliver 입니다. 이번 글에서는 최소 신장 트리 (MST, Minimum Spanning Tree)에 대해 알아보겠습니다. 목차 최소 신장 트리란? 유니온-파인드 자료구조 크루스칼 알고리즘 정리 최소 신장 트리란? 최소 신장 트리(MST, Minimum Spanning Tree)에 대해서 알아보자. 트리(Tree)란? 트리(Tree)란 노드 N개와 N-1개의 간선으로 이루어져 있으며 모든 노드가 서로 연결되어 있는 구조이다. 즉, 트리는 그래프에 포함되는 개념이며 그래프의 특별한 경우라고 할 수 있다 예를 들어, 아래의 그래프는 간선의 개수가 '노드의 개수-1'이므로 트리라고 할 수 있으며 아래의 그래프는 간선의 개수는 '노드의 개수-1'이지만 노드 D가 다른 노드들과 연결되어 있지 않으므..

[17강] 사이클이 없는 방향 그래프 (DAG)

안녕하세요 Gliver 입니다. 이번 글에서는 사이클이 없는 방향 그래프 (DAG, Directed Acyclic Graph)에 대해 알아보겠습니다. 목차 사이클이 없는 방향 그래프 위상 정렬 정리 그래프는 비선형 자료구조이기 때문에 보통 정렬이 불가능하지만 특별한 경우에는 정렬이 가능합니다. 사이클이 없는 방향 그래프일 때 정렬이 가능하며 이때의 정렬을 위상 정렬이라고 합니다. 이번 글에서는 사이클이 없는 방향 그래프(DAG)와 위상 정렬에 대해서 알아보겠습니다. 사이클이 없는 방향 그래프 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)는 말 그대로 사이클이 없는 방향 그래프를 의미한다. 사이클이 없는 방향 그래프에서는 정렬이 가능할까? 방향 그래프에서 아래와 같은 상황이..

[16강] 그래프(Graph) 최단 경로 알고리즘

안녕하세요 Gliver 입니다.이번 글에서는 그래프(Graph) 최단 경로 알고리즘에 대해 알아보겠습니다. <span style="color: #00000..

[15강] 그래프(Graph) 순회 (DFS & BFS)

안녕하세요 Gliver 입니다. 이번 글에서는 그래프(Graph) 순회 (DFS & BFS)에 대해 알아보겠습니다. 목차 그래프 순회란? 깊이 우선 탐색 (DFS) 깊이 우선 탐색 (BFS) 정리 지난 글에서 그래프를 코드로 표현하는 법에 대해서 알아보았습니다. 이번 글에서는 어떻게 그래프를 순회(탐색)할 수 있는지 알아보겠습니다. 지난 글에서 말했듯이 그래프 탐색에 있어서는 인접 리스트 방식을 이용할 예정임 그래프 순회란? 그래프 순회(탐색)란 그래프 내의 모든 노드를 한 번씩 살펴보는 것을 의미한다. 선형 자료구조에서 탐색 선형 자료구조란 순서가 있는 자료구조를 의미한다. 즉, 배열 같은 경우는 원소들이 인덱스 순으로 구성되어 있으니 선형 자료구조라고 할 수 있다. 이러한 선형 자료구조에서의 탐색은 ..

[14강] 그래프(Graph) 기본

안녕하세요 Gliver 입니다. 이번 글에서는 그래프(Graph) 기본에 대해 알아보겠습니다. 목차 그래프를 코드로 표현하기 인접 리스트 (Adjacency List) 인접 행렬 (Adjacency Matrix) 간선 리스트 (Edge List) 정리 지난 글에서 그래프는 노드(정점)와 간선으로 이루어져 있다고 설명하였습니다. 이번 글에서는 이러한 그래프를 어떻게 코드로 표현할 수 있는지 알아봅시다. 그래프를 코드로 표현하기 그래프를 코드로 어떻게 표현할 수 있을까? 그래프는 노드와 간선으로 구성되어 있으므로 노드와 간선을 각각 어떻게 표현할 수 있는지 살펴보자. 노드는 하나의 정점으로 노드의 개수만큼의 공간으로 표현할 수 있다. 간선은 노드와 노드를 선을 잇는 것이므로 간선 1개는 노드 2개로 표현할 ..

[13강] 그래프(Graph)를 배우는 이유

안녕하세요 Gliver 입니다. 이번 글에서는 그래프(Graph)를 배우는 이유에 대해 알아보겠습니다. 목차 그래프란 무엇인가? 그래서 그래프가 어디에 쓰이는데? 그래프를 배우는 이유 그래프 공부의 상한선 그래프란 무엇인가? 정점과 간선으로 이루어진 구조를 그래프(Graph)라고 칭한다. (위키피디아) 보통 정점은 node 또는 vertex, 간선은 edge라고 부른다 아래의 그림1은 정점과 간선이 둘 다 존재하므로 그래프이지만, 그림2는 간선이 존재하지 않으므로 그래프가 아니다. 간선의 방향 유무에 따라 방향 그래프, 간선의 가중치 유무에 따라 가중 그래프, 서브 그래프를 컴포넌트라고 하는 등 그래프는 굉장히 다양한 개념을 가지는 데 이는 다음 장에서 살펴보도록 하겠다. 그래서 그래프가 어디에 쓰이는데..