Computer Science
-
Union-Find(합집합 찾기)란?Computer Science/Algorithm 2020. 1. 23. 22:12
Union-Find 란? union-find 연산은 Kruskal의 알고리즘에서만 사용되는 것은 아니고 일반적으로 널리 사용된다. union(x, y) 연산은 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합의 합집합을 만든다. find(x)연산은 원소 x가 속해있는 집합을 반환한다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 위와 같이 여러 개의 노드가 연결되지 않은 채로 있다고 가정하자. 여기서 union(1, 4)와 union(5, 2)를 하면 아래와 같은 집합으로 변환된다. {1, 4}, {5, 2}, {3}, {6}, {7}, {8} 위와 같이 합쳐지는 것이다. 더 이해가 필요하기 때문에 구체..
-
Kruskal 알고리즘이란?Computer Science/Algorithm 2020. 1. 23. 22:11
Kruskal 알고리즘 Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 방법은 알고리즘 설계에서 있어서 중요한 기법 중의 하나이다. 탐욕적인 방법이란 선택할 때마다 그 순간 가장 좋았다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법이다. 탐욕적인 알고리즘에서 순간의 선택은 그 당시에는 최적이다. 하지만 최적이라고 생각했던 지역적인 해답들을 모아서 최종적인 해답을 만들었다고 해서, 그 해답이 반드시 지역적으로 최적이라는 보장은 없다. 하지만 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하여, 각 단계..
-
최소 비용 신장트리(MST, Minimum Spanning Tree)란?Computer Science/Algorithm 2020. 1. 23. 19:41
신장트리 신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 또한 사이클을 포함해서는 안된다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 신장 트리는 깊이 우선이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 또한 신장트리는 그래프의 최소 연결 부분 그래프가 된다. 여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다. n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며 (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 트리가 된..
-
힙 정렬(Heap sort) 란?Computer Science/Data_Structure 2020. 1. 16. 03:10
힙 정렬(Heap sort) 힙 정렬은 최대 힙을 이용하면 가능하다. 예전에 힙(heap) 관련 글을 썼던 내용과 같이 보면 된다. https://devlog-wjdrbs96.tistory.com/43?category=824010 힙(heap) 이란 ? https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html [자료구조] 힙(heap)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 그림같은 자료를 가져다 쓴 곳입니.. devlog-wjdrbs96.tistory.com [5, 4, 2, 1, 7, 3, 9, 6, 3, 2] 배열이 존재한다고 가정할 때 데..
-
퀵 정렬(quick sort)Computer Science/Data_Structure 2020. 1. 8. 22:36
퀵 정렬의 개념 퀵 정렬(quick sort)은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵정렬도 분할-정복(divide and conqure)에 근거한다. 퀵 정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬하는 전형적인 분할-정복법을 사용한다. 그러나 합병 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비균등하게 분할한다. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 처음에 리스트의 첫 번째 요소인 5를 피벗(pivot)으로 정하였다. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 ..
-
합병 정렬(merge sort) 란?Computer Science/Data_Structure 2020. 1. 7. 16:45
합병 정렬의 개념 합병 정렬(merge sort)는 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다. 합병 정렬은 분할 정복(divide and conquer) 기법에 바탕을 두고 있다. 분할 정복 기법은 대게 순환 호출을 이용하여 구현된다. 분할(divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 통합한다. 위의 과정을 그림으로 보면서 이해해보자. 다시 말하면, 위와..
-
버블 정렬(bubble sort) 란?Computer Science/Data_Structure 2020. 1. 7. 04:22
버블 정렬의 원리 버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이러한 리스트의 비교-교환 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이러한 비교-교환 과정은 전체 숫자가 전부 정렬될 때까지 계속한다. 바로 자바로 구현해보자. public class BubbleSort { public static void main(String[] args) { int[] list = {7, 4, 5, 1, 3}; int tmp = 0; // 버블 정렬 for (int i = list.length - 1; i > 0; --i) { for (int j = 0; j < i; +..
-
삽입 정렬(insertion sort) 란?Computer Science/Data_Structure 2020. 1. 7. 03:58
삽입정렬의 원리 삽입 정렬(insertion sort)은 손안의 카드를 정렬하는 방법과 유사하다. 우리는 카드 게임을 할 때, 새로운 카드가 들어오면 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다. 삽입 정렬은 처음에 2번 째 위치의 값을 key로 정해서 시작한다. key 값을 자신의 왼쪽에 놓인 것들과 하나씩 비교하면서 자신의 위치를 찾으면 그 자리의 있는 것과 자리를 바꾸게 된다. 자바로 삽입 정렬을 구현해보자. 삽입 정렬의 복잡도 분석 삽입 정렬의 복잡도는 입력 자료의 구성에 따라서 달라진다. 최선의 경우는 먼저 입력자료가 이미 정렬되어 있는 경우는 가장 빠르다. 최악의 경우는 입력 자료가 역순일 경우이다. 최선의 경우 삽입 정..