도시 분할 계획
문제 - 도시들이 서로 연결된 간선이 주어진다. - 간선으로 도시들 간 그룹을 만든다. - 그룹을 두개로 나눌 것이다 - 각 그룹은 적어도 하나의 도시로 이루어진다. - 간선 비용을 최소로 하고 싶다. 아이디어 - 그룹 지은 후에 선을 하나 삭제 시 그룹은 두개로 나뉜다. 코드 public class Question2 { public static void main(String[] args){ int[][] data = { {1, 2, 3}, {1, 3, 2}, {3, 2, 1}, {2, 5, 2}, {3, 4, 4}, {7, 3, 6}, {5, 1, 5}, {1, 6, 2}, {6, 4, 1}, {6, 5, 3}, {4, 5, 3}, {6, 7, 4} }; Arrays.sort(data, Comparat..
팀 결성
문제 - 학생들이 0번부터 N번까지 존재한다. 팀 합치기, 같은 팀 여부 확인 연산을 실행하라. - 데이터가 주어질때, 앞자리가 0이면 합치기 연산, 1이면 같은 팀 확인 여부 연산을 실행한다. 구현 - 서로소 집합 알고리즘 - 경로 최적화 코드 public class Question1 { public static void main(String[] args){ int[][] data = { {0, 1, 3}, {1, 1, 7}, {0, 7, 6}, {1, 7, 1}, {0, 3, 7}, {0, 4, 2}, {0, 1, 1}, {1, 1, 1} }; int[] parents = new int[8]; for(int i=0; i parent2) ? parent2 : parent1; parents[parent2..
