Algorithm/Concept

Shell Sort란? Insertion Sort를 기반으로 합니다. 서로 멀리 떨어져 있는 순자들을 정렬(insertion sort로)하기 시작하여 점점 두 숫자들 사이의 거리(gap)을 좁혀서 정렬합니다. 최종적으로 gap=1이 되면, 원래의 insertion sort를 실행하는 것과 동일합니다. Not stable하며 In-place 알고리즘 입니다. Gap, Gap Sequence Gap 정렬할 원소들이 떨어져 있는 거리입니다. 처음에는 큰 gap을 사용하여 시작하지만, 점점 작게 만들고, 최종적으로는 1이됩니다. Gap Sequence 주어진 시작 숫자부터 gap만큼 떨어진 모든 숫자들의 집합입니다. 같은 gap sequence에 속하는 숫자들을 insertion sort로 정렬합니다. Pass..

Insertion Sort란? Selection Sort처럼 정렬 중간 과정에 데이터가 두 부분으로 나눠 집니다. Stable하며 In-place한 정렬입니다. 왼쪽에는 정렬이 된 데이터입니다. 오른쪽은 정렬이 되지 않은 데이터입니다. 오른쪽 데이터의 제일 앞 숫자를 그 왼쪽의 정렬된 데이터의 제 위치에 삽입합니다. 중간의 모든 데이터는 오른쪽으로 한 칸씩 이동합니다. Insertion Sort sorting 과정 Insertion Sort 코드 #include using namespace std; #define MAX_SIZE 1000 void insertionSort(int a[], int n); int main() { int numTestCases; scanf("%d", &numTestCases);..

Comb Sort란? Bubble Sort에서 거북이(turtle) 데이터를 줄이고자 고안해낸 알고리즘입니다. 토끼(rabbit) 데이터는 bubble sort에서 문제가 되지 않습니다. Not stable하면서 In-place한 Algorithm입니다. Bubble Sort에서는 인접한 두 데이터의 크기를 비교합니다. 비교하는 두 데이터의 거리를 gap이라 합니다. Bubble sort에서는 바로 인접한 데이터를 비교하기때문에 gap이 1입니다. Comb sort gap의 크기를 1보다 크게합니다. bubble sort의 각 pass가 진행됨에 따라 gap의 크기를 줄여갑니다. "shrink factor"를 k 만큼 줄여갑니다 gap의 크기 : $$ [\frac{n}{k},\frac{n}{k^2}, \..

Selection Sort란? 기본 아이디어 정렬 중간 과정에서 데이터가 두 부분으로 나누어집니다. 왼쪽 데이터는 정렬이 된 데이터 오른쪽 데이터는 정렬이 되지 않은 데이터 Not stable한 알고리즘이면서 In place 알고리즘입니다. 오른쪽 데이터에서 제일 작은 데이터를 검색하여 선택하고 오른쪽 데이터의 제일 앞 숫자를 그 숫자랑 교환합니다. 정렬 과정 Selection Sort 코드 #include #include #define MAX_SIZE 1000 using namespace std; void selectionSort(int a[], int n); int main() { int numTestCases; scanf("%d", &numTestCases); for (int i = 0; i < n..

Bubble Sort Algorithm 정렬 알고리즘 중 기본적인 알고리즘 중 하나로 인접한 두 숫자를 비교하여 두 수의 정렬 순서가 맞지 않은 경우에 swap을 하는 알고리즘입니다. 마치 깊은 물속의 큰 물방울이 표면으로 떠 오르는 것과 같이 큰 데이터들이 배열의 왼쪽에서 오른쪽으로 이동하기 대문에 bubble sort라고 부른다고 합니다. 해당 알고리즘은 stable한 Algorithm이면서, In-Place한 Algorithm입니다. Stable: 정렬 이후 입력된 순서 그래도 유지가 되는가? In-place: 데이터를 저장하는 메모리 이외는 상수 크기의 메모리만 필요하는가? 평균적인 시간 복잡도는 O(n^2)입니다. Pass 맨 왼쪽 인접한 두 숫자를 비교하기 시작합니다 맨 끝 인접한 두 숫자를 ..

플로이드 워셜 알고리즘은 최단경로 알고리즘 중 하나로 다익스트라 알고리즘과 더불어 제일 많이 언급되는 알고리즘 중 하나입니다. 최단 경로 알고리즘을 다시 공부하면서 공부했던 내용을 포스팅 하고자 글을 작성하게 됐습니다. 플로이드 워셜 알고리즘이란? 모든 정점 사이의 최단 경로를 찾는 알고리즘입니다. 최단 경로 알고리즘인만큼 최당경로는 길이 순으로 구해집니다. 플로이드 워셜 알고리즘의 과정입니다. 1. 하나의 정점에서 다른 정점을 바로 갈 수 있으면 최소비용을 설정하며, 갈 수 없다면 INF로 무한대 값을 배열에 값으로 저장합니다. 2. 3중 for 문을 통해 거쳐가는 정점을 설정 한 후 해당 정점을 거쳐가서 비용이 줄어든느 경우에는 값을 바꿔줍니다. 3. 위 과정을 계속해서 반복하여 모든 정점 사이의 최..

해당 내용은 기본적인 Network Flow 알고리즘 중 하나인 Max Flow Algorithm을 기반으로 작성하였습니다. 2022.07.18 - [알고리즘 개념] Network Flow(네트워크 플로우) Edmonds-Karp Alogorithm [알고리즘 개념] Network Flow(네트워크 플로우) Edmonds-Karp Alogorithm Network flow 개념 네트워크 플로우란 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정 할 수 있는 알고리즘입니다. 즉, 각 간선은 데이터가 흐를 수 잇는 정해진 용량으 sunho99.tistory.com MCMF 란? MCMF(최소 비용 최대 유량) 알고리즘은 최대 유량을 사용하는 알고리즘상황에서 추가적으로 간선의 비용까지 ..

Network flow 개념 네트워크 플로우란 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정 할 수 있는 알고리즘입니다. 즉, 각 간선은 데이터가 흐를 수 잇는 정해진 용량으로 제한되어 있으며, 이를 최대한 양으로 얼마나 흐르게 할 수 있는 지 확인 할 수 있는 알고리즘입니다. 해당 vertex 사이의 간선에 최대용량 제한이 있다 생각하시면 되겠습니다. 예시를 들자면 물을 시작점에서 끝지점까지 흐를 때 얼마나 많은 물이 흐를 수 있는지, 또는 택배 물류 시스템 등으로도 사용 할 수 있습니다. 표현 방식은 주류 유량, 용량으로 표현합니다. flow network : 간선에 용량이라는 속성이 있는 그래프 입니다. source : 유량이 시작하는 정점입니다. sink : 유량이 도착..