알고리즘

프로그램 개요 : C 언어를 사용한 크러스컬 알고리즘(Kruskal Algorithm) 구현. 붕괴법칙을 적용하지 않은 크러스컬 알고리즘. 붕괴법칙을 적용한 크러스컬 알고리즘 프로그램 구조 및 설계: 이전 글과 이어지는 포스팅입니다. 프로그램의 구조와 설계 방법은 아래 링크에서 보실 수 있습니다. 2021.04.09 - [알고리즘] - 크러스컬 알고리즘 구현 1 (붕괴법칙을 적용하지 않은 방법) 참고로 아래 코드에서 붕괴법칙(collapsing rule)을 적용하여 문제를 해결하는 알고리즘이 있는데, 붕괴법칙이란 임의의 노드 i에 대해 find 연산을 한다고 하였을 때, 정상적으로 루트를 찾았다면 i부터 루트까지의 경로에 있는 모든 노드들을 그 루트의 자식으로 만드는 것을 말합니다. 즉, i에 대해 find 연산을 한 번 하였다면 그 이후부터는 i부터 루트까지의 경로에 있는 모든 노드들이 한 번에 자신의 루트를 찾을 수 있다는 뜻이 됩니다. ...

프로그램 개요 : C 언어를 사용한 크러스컬 알고리즘(Kruskal Algorithm) 구현. 붕괴법칙을 적용하지 않은 크러스컬 알고리즘. 붕괴법칙을 적용한 크러스컬 알고리즘 크러스컬 알고리즘에 대한 설명은 아래 링크의 이전 글에서 볼 수 있습니다. 2020.07.02 - [알고리즘] - 크러스컬(Kruskal) 알고리즘 이 글에서는 예로 주어진 그래프에 대해서 크러스컬 알고리즘으로 문제를 해결하는 방법과 코드를 작성하였습니다. 입력 가중치 그래프 : 입력 파일 : 입력 데이터 입력 데이터가 들어있는 .txt 파일입니다. [graphInf.txt 0.00MB](https://blog.kakaocdn.net/dna/9GWpl/btq2iFfdTGn/AAAAAAAAAAAAAAAAAAAAAPR1afPSYRSSngG_pTeKxCHZPt50vsapwyoi0hUqhYlq/graphInf.txt?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1788188399&allow_ip=&allow_referer=&signature=tBqiAllXzExVIgPQgq2UUYjZeLk%3D&attach=1&knm=tfile.txt) 프로그램 실행 결과 : ...

크러스컬(Kruskal) 알고리즘이란? 크러스컬 알고리즘은 최소 비용 신장 그래프를 찾는 알고리즘 입니다. 변의 개수를 E, 꼭지점의 개수를 V라고 한다면 크러스컬 알고리즘은 O(ElogV)의 시간 복잡도를 갖습니다. 크러스컬의 MST(욕심쟁이 방법) 알고리즘 간략 코드 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 edge_set kruskal_MST(edge_set E, int n) { sort(E); // 간선 정렬 edge_set MST_E = { }; for (i=0; i<n; i++) init_set(i); // n개의 집합(트리)을 생성 while(MST_E의 간선 수 < n - 1) { (u, v) = E의 최소 가중치 간선; E = E - {(u, v)}; if(find(u) != find(v)) // u와 v가 다른 집합(트리) 원소 { MST_E = MST_E ∪ {(u, v)}; // 간선 추가 union(u, v); // 두 집합(트리)을 합병 } } return MST_E; } - 예제 - ...

합병 정렬(Merge Sort)이란? 분할 정복 알고리즘(=Divide and conquer algorithm 즉, 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘입니다.)의 하나로 O(n log n)의 시간 복잡도를 가지고 있습니다. 합병 정렬의 작동 알고리즘은 아래와 같습니다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 이해가 잘 안간다면 아래 애니메이션을 통해 작동 원리를 쉽게 이해할 수 있습니다. ...

삽입 정렬(Insertion Sort)이란? 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다. 삽입 정렬의 시간 복잡도는 O(n2)이며 안정 정렬입니다. 또한 배열이 길어질수록 효율이 매우 떨어지지만 구현이 간단하다는 장점이 있습니다. 삽입 정렬의 예 삽입 정렬의 애니메이션 -Simpsons contributor- 삽입 정렬 알고리즘을 구현하기 전에 의사코드(Pseudocode)로 먼저 이해를 하고 코드를 작성하는 것이 더 쉽게 작성할 수 있을 것입니다. Pseudocode : 1 2 3 4 5 6 7 8 9 //InsertionSort pseudo code InsertionSort(A,n) // sort A[1...n] for j <- 2 to n do key <- A[j] i <- j-1 while i>0 and A[i]>key do A[i+1] <- A[i] i <- i-1 A[i+1] <- key C코드 : ...