공부(2018~2019) - 스킨변경전

1197번 최소 스패닝 트리(MST) MST는 모든 노드가 사이클 없이 최소 비용으로 모두 연결된 트리를 말한다. 간선은 Vertex - 1이 된다. MST 알고리즘에는 Kruskal 알고리즘과 Prim 알고리즘이 있다. Kruskal 알고리즘은 Edge들의 가중치로 오름차순으로 정렬하고 가장 적은 간선을 선택한다. 이때 사이클이 발생하면 선택하지않는다. Prim 알고리즘은 다익스트라처럼 해당 정점의 인접 정점을 탐색하고 업데이트 한 뒤 가장 최저비용을 선택한다. 다익스트라는 최단경로이고 Prim은 각 정점들을 N-1개의 간선으로만 구성되는 그래프를 만드는 것에 차이가 존재한다. 또한 다익스트라는 경로를 누적하지만 Prim은 경로의 가중치를 누적하지 않는다 Prim 1 2 3 4 5 6 7 8 9 10 ..

1. 1717번 집합의 표현기본 UnionFind 문제 , UnionFind는 어떤 노드가 있을 때 루트의 크기를 비교해서 하나의 집합으로 만들어 주는 알고리즘이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java..

1. 2748번 피보나치2 BigInteger 문제, 처음에는 단순히 int로 접근해서 풀었는데 틀렸습니다가 나왔다. 50번째 피보나치를 할 경우 int 범위가 넘어버렸다.BigInteger는 거의 무한대의 가까운 정수를 나타낼 수 있다. 주의할점은 사칙연산은 모두 함수를 이용하여야 한다.1234567891011121314151617181920212223242526272829303132import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.math.BigInteger;import java.util.StringTokenizer; public class Main { public st..

1. 2252번 줄세우기기본 위상정렬 문제, 위상정렬은 우선순위에 맞게 정렬하는 것을 의미한다.BFS로만 접근 했을 때 1 -> 3, 2 -> 3 을 할경우 1 - > 3 - > 2 가 출력되는 문제가 있었다. 이는 우선순위를 고려하지 않은 오류이다.예를 들어 게임 상에서 1번 퀘스트와 2번퀘스트를 완료해야 3번 퀘스트를 할 수 있는 때 이 순서를 묻는 문제와 같다.먼저 해야하는 퀘스트를 완료하면 3번 퀘스트의 우선순위를 하나씩 낮춰서 모두 클리어 했을떄 3번 퀘스트가 활성화 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667..

1. 14502번 연구소BFS, DFS 중급 문제, DFS를 사용하여 벽을 세울 경우 백트레킹이 들어가야 한다.처음에 for문을 이용하여 벽을 세우려고 했지만 4중 for문에 또 DFS , 안전영역 체크 까지 for문이 많이 중첩되어 문제가 발생했다,벽을 세울때 DFS와 백트래킹을 이용하여 벽을 세우고 -> DFS (벽 3개가 될떄지 ) - > 벽 3개가 되면 BFS를 호출하고 끝나면 백트래킹DFS로 영역을 확장하는 것 이외에 벽세우기 같은 순차적으로 반복했을 때도 사용 가능하다는 것을 알게된 문제 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626..

1. 5014번 스타트링크기본 BFS 문제, 주의할점은 같은 층 일경우 0 , 층수가 100000층까지 가기 때문에 초기 min값을 크게 잡아야 한다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer; public..

1. 1991번 트리 순회기본 이진트리 알고리즘, preorder ( Root -> L -> R ) inorder ( L -> Root -> R ) postorder ( L -> R -> Root ) 배열의 인덱스를 이용해서 트리를 생성하였다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Ar..

1. 2589번 보물섬기본 BFS 문제, 최단가리는 BFS를 이용하여 접근하는 편이 좋다.모든 육지에 대해 하나하나 BFS로 탐색하여 가장 큰 값을 출력한다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;im..

1. 2468번 안전영역기본 DFS 문제, 비가 오는 모든 경우를 판단하고 모든 영역이 잠기지 않을때까지의 안전영역 중 가장 많은 영역을 출력주의할점은 비가 오지 않는 경우도 포함 해야한다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static boolean[][] visited; sta..

1. 11758번 CCW외적을 이용하여 벡터 간의 방향성을 알려주는 알고리즘 이다.x1y2 + y1x3 + x2y3 - (x3y2 + x1y3 + y1x3) 이값이 0보다 크면 1(반시계 방향) 작으면 -1(시계 방향) 같으면 0(일직선) 나타낸다.12345678910111213141516171819202122import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws NumberFormatException, IOException..

1. 1931번 회의실최적의 경우를 이용하는 그디리 알고리즘 문제, 끝나는 시간을 판단하여 회의실을 배정 해야한다.주의할점은 정렬을 두번 해주어야 한다. 끝나는 시간이 같은데 더 느린 경우가 생길 수 있기 때문이다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import ..

1. 11399번 ATM간단한 정렬문제, 2중 for문을 이용해서 풀었지만 for문 하나로도 풀이가 가능하다.ex) 정렬 후 N - i 만큼 곱해서 더해주면 된다 1 2 2 3 3 -> 1 * 5 + 2 * 4 + 2 * 3 + 3 * 3 + 3 * 3 즉 N명이 기다리는 시간을 합산한다. 1등 1분씩 5명 2등 2분씩 4명 ~~1234567891011121314151617181920212223242526272829import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Mai..