Dogfootruler Kim

신장트리(Spanning Tree)란? 1. N개의 정점 2. N-1개의 간선 3. 사이클이 존재하지 않는다. 위 3가지 조건을 갖춘 트리를 신장트리라고 한다. 최소 신장 트리란? (Minimum Spanning Tree) 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리를 말한다. MST 알고리즘 종류 크루스칼(Kruskal) - 간선중심 프림(Prim) - 정점 중심 따라서, 간선 적으면 크루스칼, 간선 많으면 프림을 사용하면 된다. 크루스칼 알고리즘 - 간선을 하나씩 선택해서 MST를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 - 사이클 ..

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 및 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; public static void main(String[] args) throws NumberFormatException, IOExceptio..

풀이 및 소스코드 좌표에 대한 가중치들을 만든 후, union-find와 함께 크루스칼 알고리즘을 사용하면 된다 ! 마지막에 res 를 Math.round 해서 반올림 해줘야한다. 아니면 테케 일부를 틀리게 된다 ㅠ = 나 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Solution { static class Island implements Comparable{ int x, y; double w;..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 및 소스코드 골드문제를 아직 많이 못풀어봐서 언제나 어렵다 ㅠㅠ........흡 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Prio..

문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 풀이 및 소스코드 처음에는 간선을 추가하는 것만 생각해서 LinkedList 를 사용해서 풀었다. 그랬더니 시간초과가 났다 ㅠㅠ 혹시나 하는 마음에 ArrayList로 바꿔봤더니 해결됐다. 그 이유는 최단경로를 찾기위해 get을 많이 사용하는데, LinkedList의 get 시간복잡도가 O(n) 이기 때문이다. 아래의 표는 똑똑하신 뷴께서 보내주신 내 질문에 대한 ..

풀이 및 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Solution { static int n,m; static int[] p; public static void make() { for(int i=0;i

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 및 소스코드 여기서 한가지 자칫 실수할 것이 7 6 100 400 300 100 500 101 400 답: 500 이 반례이다. 나같은 경우에는 테케만 보고 맨끝이 제일 긴 비디오라 생각하여서 시작을 배열의 끝인 400부터 start로 잡고 갔는데, 이러한 반례가 존재한다. 따라서 리스트의 최대값을 찾고, 그것을 start로 해주고, end는 리스트의 총합을 넣어준다. 또한, 블루레이의 최솟값..

풀이 및 소스코드 union-find 사용하면 금방 해결할 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Solution { static int[] p; static int n,m; public static void make() { for(int i=0;i