퀵정렬은 분할 정복 기법을 씁니다.

문제 링크

• http://icpc.me/14496

문제 링크

• http://icpc.me/14495

문제 링크

• http://icpc.me/14494

작동 과정

버블정렬은 인접한 원소를 비교/교체 하고,
선택정렬은 가장 작은 값을 선택해서 앞으로 넣어주면서 정렬을 했습니다.
삽입정렬은 모든 자료를 앞에서 부터 차례대로 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식으로 정렬을 진행합니다.

컴퓨터의 3대 하드웨어

• CPU (연산/제어 장치) - 명령어를 실행하는 장치
• RAM (주기억장치) - 현재 실행 중인 프로그램이 기억되는 장치
• 하드디스크 (보조기억장치) - 모든 데이터와 프로그램을 저장하는 장치

작동 방식

버블 정렬은 인접한 두 수를 비교해서 정렬을 했습니다.
반면, 선택 정렬은 최소값을 선택해 맨 앞으로 옮겨주는 방법으로 정렬을 합니다.

작동 과정

버블 정렬은 인접한 두 원소를 비교해 정렬합니다.
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에 대해 다룰 것입니다.