원리 1. 정렬할 배열을 사이즈가 1이 될때까지 반으로 나눈다. (분할) 2. 나눌 수 없을때까지 나눈뒤 정렬을 한다. (정복) 3. 정렬 한 결과를 병합한다. (병합) [ 16, 11, 6, 19, 12, 2, 2, 10 ] 정렬하기에 앞서 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 모르더라도 이번 기회에 직접 이해해 보도록 하겠습니다. 분할은 배열을 절반씩 나누어서 사이즈가 1이 될때까지 나눈 것입니다. 그리고 정렬을 하고 병합을 하는 식으로 구성되어있습니다. 방식은 쉽게 이해하실 수 있습니다. 그렇다면 왜 굳이 분할을 해서 다시 합치면서 정렬을 해야할까요? 이는 아래 시간복잡도를 알아보면서 이해해보도록 하겠습니다. 구현 template vector MergeSort(co..

목차 1. 최소 신장 트리의 정의 2. Kruskal 알고리즘의 개념 3. Kruskal 알고리즘 구현 정의 최소 신장 트리 (Minimum Spanning Tree)에 대해 알아보기 전에 우선 신장 트리가 무엇인지 알아보겠습니다. 신장 트리(Spanning Tree)는 무방향 연결 그래프가 존재할 때, 그 그래프에서 모든 정점을 포함하도록 간선을 부분적으로 선택하여 만들 수 있는 부분 그래프 입니다. 어떤 그래프가 정점 V개와 E개의 간선을 가지고 있다고 가정하면 신장 트리의 정점과 간선의 개수는 각각 V와 V-1이 되겠습니다. 최소 신장 트리는 그 중에서도 가중치가 있는 그래프일 때를 고려합니다. 그래프의 간선마다 가중치가 있을 때 간선의 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라고 합..

원리 1. 집합의 최댓값을 구해서 최대값만큼의 메모리를 차지하는 카운팅 배열을 만든다. 2. 각원소의 개수를 카운팅시킨다 3. 카운팅 배열의 누적합을 구한다. 4. 카운팅 배열을 통해 순서대로 수를 나열한다. [ 15, 13, 10, 7, 5, 5, 1, 0, 7 ] 카운팅 배열에는 다음과 같이 구성될 수 있습니다. Index 0 1 5 7 10 13 15 count 1 1 2 2 1 1 1 다음을 누적합의 표입니다. Index 0 1 5 7 10 13 15 count 1 2 4 6 7 8 9 이때, 누적합을 구하는 이유는 어느 인덱스에 원본 원소가 들어갈지 순서를 강제하기 위해서 입니다. 정렬된 원소들이 들어갈 배열의 인덱스를 카운팅배열의 데이터 - 1로 설정 해줌으로서 정렬 해줄 수 있습니다. 예를들..

원리 1. 0번부터 n번 인덱스의 데이터를 차례대로 선택하자 2. 선택한 인덱스부터 0까지 인접한 인덱스를 비교하자 3. 만약 인덱스가 낮은 원소가 더 크다면 교환하고 아니라면 탈출한다. (오름차순기준) [ 70, 55, 30, 47, 66 ] (70) 55 30 47 66 --> "70" 55 30 47 66 70 (55) 30 47 66 --> "55" 70 30 47 66 55 70 (30) 47 66 --> "30" 55 70 47 66 30 55 70 (47) 66 --> 30 "47" 55 70 66 30 47 55 70 (66) --> 30 47 55 "66" 70 정렬 후 : [ 30 47 55 66 70 ] 구현 for (int i = 0; i < n - 1; ++i) { int fix ..

원리 1. 정렬되지 않은 중 원소를 가장 작은 원소를 탐색하자 2. 가장 작은 원소를 정렬 되지 않은 원소 맨앞으로 보내자 [ 70, 55, 30, 20, 47 ] | 70, 55, 30, 20, 47 --> 70, 55, 30, (20), 47 (선택) 20, | 70, 55, 30, 47 --> 20, 70, 55, (30), 47 (선택) 20, 30, | 70, 55, 47 --> 20, 30, 70, 55, (47) (선택) 20, 30, 47, | 70, 55 --> 20, 30, 47, 70, (55) (선택) 정렬 후 : [ 20, 30, 47, 55, 70 ] 구현 for (int i = 0; i < n - 1; ++i) { int min_idx = i; for (int j = i + 1..

알고리즘 문제를 풀다보면 흔히 제한 시간 초과 (Time Out)을 경험할 수 있습니다. 이번 포스팅에서는 어떻게 하면 제한 시간 초과를 피할 수 있는지 그 방법에 대해서 다루어보고자 합니다. 보통 시간복잡도를 표기할 때 빅오 표기법 (Big-O Notation)으로 표기하는 것이 일반적입니다. 대표적인 시간복잡도들을 대소 관계로 나타낸 그래프는 아래의 그림과 같습니다. 그래프를 보면 주어진 입력의 크기인 N이 점점 커짐에 따라 시간복잡도의 차이가 수행시간에 큰 영향을 준다는 것을 알 수 있습니다. 상수 시간인 O(1) 이 가장 좋고, 그 다음으로는 O(logN) 이후로 O(N) 순서이며, O(2N) 과 O(N!) 과 같은 지수시간 이상의 알고리즘 들은 N이 굉장히 작은게 아니라면 제한시간 내에 문제를 ..