stonesy

📖최소신장트리 최소신장트리란 1)모든 정점을 포함하면서 2)간선의 가중치 합이 최소인 트리를 말한다. 최소신장트리를 찾는 알고리즘 중 대표적으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다. 🔍Kruskal 알고리즘 간선 중심 → edgeList가 필요 1. 최초 모든 간선을 가중치에 따라 오름차순으로 정렬 2. 가중치가 낮은 간선부터 선택하면서 트리를 증가시킨다. 이때, 사이클이 존재하면 남아 있는 간선 중 그 다음으로 가중치가 낮은 선택 =>N-1개의 간선이 선택될 때까지 2반복 *서로소 집합(Disjoint-set)을 이용한 Kruskal 알고리즘의 구현 서로소 집합(Disjoint-set)은 중복 포함된 원소가 없는 집합을 의미한다. import java.io.BufferedReader; ..

📖순열, 조합, 부분집합 1. 순열(Permutation) : 순서에 따라 배열된 원소들의 모든 가능한 조합(순서 O, 중복 X) - 주어진 원소들을 나열하는 경우의 수 계산 2. 조합(Combination) : 순서에 상관없이 선택된 원소들의 모든 가능한 조합(순서X, 중복X) - 주어진 원소들을 뽑는 경우의 수 계산 3. 부분집합(Subset) : 어떤 집합의 일부 원소로 이루어진 집합 - 주어진 집합의 모든 부분집합 계산 🔍순열 구현 1. 중복원소를 boolean 배열을 이용해서 확인 import java.util.Arrays; // 중복 원소를 배열을 이용해서 체크하기 // 9P9 : 0.01 (안전) // 10P10 : 0.1초 컷(약간 위험) public class PermutationTest..