코드 깎는 개발자

[알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm) 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 즉, 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다. 다음 노드들을 모두 한번씩 들르는 최소 경로를 알아보자! 비용이 짧은 순서대로 그래프에 포함시키자!! 일단 모든 노드를 최대한 적은 비용으로 연결만 시키면 되기 때문에 모든 비용의 정보를 오름차순으로 정렬한 뒤에 비용이 작은 것부터 차근 차근 그래프에 포함시키면 된다. 단 사이클을 형성하는 경우는 포함에서 제외한다. 소스코드 구현 (C++) #include #include #include using namespace std; int GetParent(int parent[], int x) { if (paren..

[알고리즘] 합집합 찾기 (Union Find) 대표적인 그래프 알고리즘이며 서로소 집합(Disjoint-Set) 알고리즘이라고도 부른다. 여러개의 노드가 존재할 때 두개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판변하는 알고리즘이다. 숫자들을 설정하고 깊이 우선 탐색하는 프로그램을 작성하자! 부모를 합칠 때 일반적으로 더 작은 값으로 합치며 이것을 합침(Union)이라고 하며 노드를 선택해서 그 노드가 같은 합침에 속해있는지를 찾는 알고리즘이다. 소스코드 구현 (C++) #include using namespace std; //부모 찾기 int GetParent(int parent[], int x) { if (parent[x] == x) return x; return pare..