KalelPark's LAB

Merge sort 이란? 분할 정복(divide and Conquer)에 속하는 알고리즘 중 하나로, "폰 노이만(von Neumann)"이라는 사람이 제안하였다. 하나의 배열을 분할하고, 분할된 배열을 정렬하고, 분할된 배열을 합하여, 최종적으로 정렬하는 알고리즘이다. 시간복잡도(Time Complexity) - O(nlogN) Merge sort 동작 1. 배열을 중간 index를 기준으로 좌, 우로 나눕니다. (부분 배열이 1개가 남을 때까지 계속해서 반복.) 2. 이후, 합병을 진행하는데 배열 내 요소의 대소 비교를 한 후, 배열을 합병합니다. Merge sort with C/C++ void merge(element initList[]. int i, int m, int n) { int j, k,..

Binary Search Tree 이란? 이진 탐색 트리(binary search tree)란 연결리스트(linked list)를 결합한 자료구조의 일종이다. 이진 탐색(binary search)의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제가 가능합니다. 이진 탐색(binary search)의 경우 탐색에 소요되는 계산복잡성은 O(longN)으로 빠르지만, 입력 및 삭제가 불가능하고, 연결리스트의 경우 입력, 삭제에 필요한 복잡도는 O(1)이지만, 탐색을 하는데, O(N)의 시간이 걸리는데, 탐색과 입력 및 삭제를 효율적으로 활용해보고자 하는 것이, 이진 탐색 트리(Binary Search Tree)입니다. 시간 복잡도 Common case : O(h) Worst case : O(n) ..

Heap 이란? 완전 이진트리(Complete Binary Tree)의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬(느슨한 정렬 상태) 상태를 유지합니다. - 큰 값이 상위 레벨에 있으며, 작은 값은 하위 레벨에 있다고 보면 됩니다. - * Max Heaps = Max trees and also Complete binary tree Priority Queue 이란? 큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First in First Out 형식의 자료구조 이다. 우선순위 큐(Priority Queue)는 일반적으로 힙(Heap)을 이용하여 구현합니다. 일반적으로, inse..

Dijkstra's Algorithm 이란? 최단 경로(Shortest Path) 탐색 알고리즘이다. 한 정점(Vertex)에서 다른 정점(Vertex)까지의 최단 경로를 구하는 알고리즘 중 하나이다. 최단 경로(Shortest Path)를 찾는 과정에서, 도착 정점(Vertex) 뿐만 아니라, 다른 정점(Vertex)까지 최단 경로로 방문하여, 각 정점(Vertex)까지의 최단 경로를 찾게 됩니다. 시간복잡도 (Time Complexity) - using priority queue case : O(ElogE) - common case : O(n^2) Dijkstra's Algorithm 동작 1. 시작 정점(Vertex)를 설정합니다. (시작 정점(Vertex) 비용 : 0) 2. 시작 정점(Verte..

Insertion sort 이란? 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 비분과 비교하여, 위치를 찾아 삽입함으로써, 정렬을 완성합니다. 시간복잡도 (Time Complexity) - best case : O(n) - worst case : O(n^2) * It does little work if the list is nearly sorted Insertion sort 동작 1. 배열 내에서, 2번째 위치의 값을 임시로 저장합니다. 2. 임시로 저장한 값 이전에 위치한 원소들과 비교하여, 값을 변경합니다. 3. 위의 1 ~ 2번의 과정을 계속해서 시행합니다. Insertion sort code with C/C++ void insert(element e, element a[], int i..

Bellman-Ford Algorithm 이란? 한 정점(Vertex)에서 다른 정점(Vertex)까지의 최단 거리를 구하는 알고리즘이다. 다익스트라(Dijkstra Algorithm)과 달리, 정점(Vertex) 간의 간선(edge) 비용이 음수인 경우에도 사용가능하다. 벨만 포드(Bellman-Ford)는 다이나믹 프로그래밍(Dynamic Programming)이라고도 할 수 있다. 그러한 이유는 매번 저장해놓은 최소 비용을 활용해서, 새로운 최소 비용을 갱신하기 때문이다. 벨만 포드(Bellman-Ford)는 다익스트라(Dijkstra Algorithm)보다 시간이 오래 걸리는데, 그러한 이유는 최소 비용을 가지는 간선(edge)만을 우선적으로 뽑는 다익스트라(Dijkstra Algorithm) 달..

Sollin's Algorithm 이란? 최소 비용 신장 트리를 구하는 알고리즘 중 하나로, Prim's Algorithm과 달리 간선(Edge)를 하나씩 선택하는 것이 아닌 동시에 여러 개의 간선(Edge)을 선택하여, Tree를 만드는 알고리즘이다. Sollin's Algorithm을 알기 전, Forest를 Sollin's Algorithm 동작 1. 각각의 단계마다, 신장 트리 집합 내 Vertex를 포함한 몇 개의 Edge를 선택합니다. (Prim's Algorithm, Kruskal's Alogrithm과 다르게, 2개 이상 Edge를 선택하는 것이 가능합니다.) 2. 각 트리는 다른 트리와 연결할 수 있는 최소 비용의 Edge를 선택합니다. (중복되는 Edge는 제거합니다.) * 만약, 비용..

Prim's Algorithm 이란? 최소 비용 신장 트리를 구하는 알고리즘 중 하나로, 가중치를 가지는 그래프에서, 가장 작은 가중치를 가지는 간선(Edge)를 시작으로 인접한 정점과 연결된 Edge들 중에서, 가장 작은 가중치를 가지는 간선(Edge)들을 선택하는 방식이다. Prim 알고리즘은, 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복됩니다. 그러므로 시간복잡도는 O(N*N) 입니다. Prim's Algorithm 동작 1. 시작 단계에서, 시작 정점만을 MST(최소 비용 신장 트리) 집합에 포함합니다. 2. MST(최소 비용 신장 트리) 집합에 포함된 정점들에 인접한 정점과 최소 간선으로 연결할 수 있는 정점을 집합에 넣어줍니다. 3. 이러한 과정을 간선이 N-1개, 즉 C..