작동 과정

버블 정렬은 인접한 두 원소를 비교해 정렬합니다.
55 07 78 12 42를 인접한 두 원소끼리 비교해 오름차순으로 정렬해보겠습니다.

1
2
3
4
5
6
7
8
9
10
11

"55 07" 78 12 42 -> swap
07 "55 78" 12 42  
07 55 "78 12" 42 -> swap
07 55 12 "78 42" -> swap
"07 55" 12 42 78  
07 "55 12" 42 78 -> swap
07 12 "55 42" 78 -> swap
"07 12" 42 55 78  
07 "12 42" 55 78  
"07 12" 42 55 78  
"07 12 42 55 78"  정렬 끝

이런 과정을 거쳐 정렬이 됩니다.
뒤쪽부터 정렬이 되어가는 것을 볼 수 있습니다.

작동 과정

크루스컬 알고리즘은 간선들 중에거 가중치가 가장 작은 간선부터 차례대로 연결해줍니다.
그래프에서 정점들만 남겨둔 상태로 시작해서 가중치가 작은 간선부터 하나씩 그래프에 채워 준다고 생각하면 이해하기 쉽습니다.

이번 글에서는 MST(Minimum Spanning Tree, 최소 신장 트리)의 간단한 개념과 Prim Algorithm에 대해 다룰 것입니다.

서론

다익스트라 알고리즘은 한 정점에서 다른 모든 정점까지 가는 최단 거리와 경로를 구하는 알고리즘입니다.
그리디 기법을 기반으로 작동하며, 음수 간선이 있는 그래프에서는 사용할 수 없습니다.

서론

플로이드 와샬 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 거리를 모두 구해줍니다.
구현이 매우 간단해서 초보자들도 쉽게 따라할 수 있습니다.

서론

위상 정렬은 그래프 중에서도 DAG에서만 사용 가능한 알고리즘입니다.
DAG는 Directed Acyclic Graph의 줄임말이며, 사이클이 없는 유향(방향) 그래프입니다.
위상 정렬은 유향 그래프의 방향성을 거스르지 않게 정점들을 나열하는 것입니다.

마치 스타크래프트에서 해처리가 있어야 스포닝 풀을 지을 수 있고, 스포닝 풀이 있어야 히드라리스크 덴과 레어를 지을 수 있는 것처럼 어떤 일을 수행하기 전에 미리 해야할 일이 있다면, 미리 수행해야 할 일을 먼저 하는 것과 같다고 볼 수 있습니다.

서론

이 글에서는 DFS와 BFS에 대해 설명할 것입니다.
DFS는 Depth First Search의 약자이며, 해석하면 깊이 우선 탐색입니다.
BFS는 Breadth First Search의 약자이며, 해것하면 너비 우선 탐색입니다.

그래프의 두 가지 표현방법

그래프의 표현 방법은 대부분 2가지 중 하나를 사용하는데, 하나는 인접 행렬, 다른 하나는 인접 리스트입니다.
인접 행렬은 말 그대로 행렬(2차원 배열)로 표현하고, 인접 리스트는 연결 리스트(Linked List) 혹은 동적 배열(ex. C++ vector 컨테이너)를 사용해 구현합니다.

그래프란?

이런 형태로 생긴 것을 그래프라고 합니다.
동그라미 부분을 Vertex(혹은 Node, 정점)라 부르고 정점끼리 이은 선분을 Edge(간선)라고 부릅니다.

이진탐색이란?

순차 탐색은 배열의 길이가 n이라면, 최대 n번 계산해야 해를 구할 수 있습니다.
이번에 다룰 이진탐색은 특정 조건만 만족하면 순차 탐색보다 훨씬 더 빠르게 해를 구할 수 있습니다.