Shortest Path 를 찾는 알고리즘으로 Prim 알고리즘을 살펴보았다. prim 은 그리디 알고리즘으로, MST(최소 신장 트리)를 만들기 위해 힙, 즉 우선순위큐를 사용했다. 두 정점 사이의 edge 거리가 작은 것 우선순위가 높도록 정했다. 이번 포스팅에서 다룰 Kruskal 알고리즘도 Shortest path를 찾는 문제다. 연결 그래프가 주어지고 MST를 구하면 되는 문제이다. Prim 알고리즘과 목적이 같지만, 구현 방법에 약간의 차이가 있다. Prim 알고리즘 포스팅: https://matt1235.tistory.com/51 문제) 다음과 같은 연결그래프가 있다. 모든 정점을 연결하는 Minimum Spanning Tree를 구하라. Prim 알고리즘은 T라는 해집합을 점차 늘려나가는 ..

저번 포스팅에서 연결그래프의 MST(Minimum Spanning Tree) 를 구하는 방법인 Prim 알고리즘에 대해 소개하고 그 정확성을 증명해보았습니다. https://matt1235.tistory.com/51 Prim 알고리즘 - 1 이번 포스팅에서는 Prim Algorithm을 소개하고, 그 정확성을 증명해보고자 한다. 다음 그림을 보자. 정점이 다섯 개가 있고 간선(edge)이 총 10개 있는 연결 그래프이다. 각 간선의 숫자는 노드에서 노 matt1235.tistory.com 이번 포스팅에서는 Prim을 구현해보겠다. => 우선순위 큐를 이용해 구현 우선순위 큐 (Priority Queue) 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 방식..

이번 포스팅에서는 Prim Algorithm을 소개하고, 그 정확성을 증명해보고자 한다. 다음 그림을 보자. 정점이 다섯 개가 있고 간선(edge)이 총 10개 있는 연결 그래프이다. 각 간선의 숫자는 노드에서 노드까지의 거리를 나타낸다. 위 그래프에서 MST(최소 비용 신장 트리)를 구하라. 용어 신장트리(Spanning Tree) 그래프 내 모든 정점을 포함하는 트리를 의미. 모든 정점이 연결되어 있어야 하고, 사이클을 포함해서는 안된다. 따라서 신장트리는 노드가 n개라면 정확히 (n-1) 개의 간선을 갖는다. 신장트리의 예시로는 다음이 있다. 이처럼 모든 노드가 연결되어 있고, 사이클을 만들지 않으면 Spanning Tree 완성이다. 간선의 수는 자연스레 (노드수 - 1) 이 된다. 우리가 위 문..

이번 포스팅에서는 선택정렬(Selection Sort) 알고리즘을 증명해보자. selection sort 는 알고리즘을 처음 접하면 알게 되는 녀석이다. 하지만 이 역시 수학적으로 엄밀하게 증명해본 적이 없어 이를 증명해보고자 한다. selection sort 소스코드 // Selection Sort int sort(int a[], int n){ int i, j, m, t; for(i=0;i k-1 이라면 a[k-1] < a[x] 가 성립한다. Proof Invariant 수학적 귀납법을 이용해 불변조건을 증명해보자. Base k=0일 때 (1)은 null condition, true. (2)도 null이므로, true. 성립할 조건이 아예 없으면 true이다. 따라서 Invariant 는 성립한다. S..

이번 포스팅 내용은 Merge Sort 의 정확성을 증명해보는 것이다. Divide and Conquer - 분할 정복 입력을 나누어 더 작은 문제를 물고, 작은 문제들의 답을 조합해 전체 문제의 답을 만든다. 아주 작은 문제는 어쨌거나 풀린다. mergeSort는 분할 정복 기법을 사용한다. 문제를 더 작은 문제로 나누고, 답을 합칠 때(merge) 재귀가 사용된다. 위처럼 "이미 Sorted 된 두 배열을 합쳐(merge) Sorted 된 배열을 만들자" 가 이 알고리즘의 아이디어이다. 재귀라고 해서 따라 들어가지 않고, 바로 알 수 있도록 증명해보는 연습을 하는 것이다. Recursive MergeSort int sort(int a[], int n){ if(n

(본문은 학교 강의내용을 바탕으로 이해한 것을 정리한 글입니다. 틀린 부분이 있다면 지적 감사하겠습니다.) 이분탐색 알고리즘, Binary Search는 기초적인 탐색 알고리즘이다. 알고리즘을 공부하다 보면 다들 한번쯤은 들어봤을 만한 녀석이다. 나 또한 처음 알고리즘을 접하고 binary search를 접했을 때에는 직관적으로는 이해하기 어렵지는 않았다. 하지만 이녀석을 정확하게 증명한 적은 없었고, 깊이 생각해본 적도 없었던 것 같다. 굳이 왜..? 라는 생각이 들지도 모르지만 학부생일때 이런 경험을 많이 하는게 나중에 도움이 될 거라 믿어 포스팅을 작성하게 되었다. Binary Search // Binary Search // a is sorted array, n: size, x: value to f..