Will Be Fine

1. 2579번 계단 오르기DP문제, 처음에는 DFS로 접근하였는데 시간초과가 발생하였다. 최대의 계단이 300개 인데 이때 수많은 경우가 발생한다. 문제에 주어진 조건을 자세히 확인한다음 경우의 수가 얼마나 발생하는지 보고 DP인지 다른 알고리즘인지 판단하는게 좋을 것 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class..

1. 11404번 플로이드기본 플로이드 워셜 알고리즘 문제, 3중 for문을 이용하여 처음 반복은 직선이 아닌 거쳐가는 부분을 뜻하며 두 세번째는 직진루트이다.모든 경로에 대한 최단거리를 구할 때 사용한다. 시간복잡도 O(V^3)모든 경로에 대한 우회루트를 계산하여 가장 작은 값을 최단경로로 사용한다12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; publi..

1. 1922번 네트워크 연결 기본 MST 문제, 정점 수 - 1 개의 간선으로 모든 정점이 연결 되는 지(최저비용으로 연결) 문제는 모두 MST 알고리즘을 사용하면 된다. Prim 알고리즘이 약 180ms 정도 빨랐다. ( Prim O( Edge log Vertex) , Kruskal O( Edge log Edge ) Prim 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889import java.io.BufferedReader;import java.io..

1. 11779번 최소비용 구하기2최소비용 구하기에서 경로와 정점개수를 추가로 출력하는 문제 (다익스트라)주의할점은 경로가 최단거리로 바뀔 수 있기 때문에 유동적으로 배열의 인덱스를 활용해서 접근해야한다.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107import java.io.BufferedReader;import java.io.IOException;import java.io..

1. 1916번 최소비용 구하기(Dijkstra) 다익스트라 알고리즘 문제, for문을 이용하는 방법과 우선순위 큐를 이용하는 방법이 있는데 우선순위 큐를 사용하는 것이 좋다. 다익스트라는 시작정점에서 인접정점의 가중치가 가장 최소가 되는 선택하는 그리디 알고리즘이다. 시작정점 -> 인접정점들의 정보 -> 최저비용 정점으로 이동 -> 인접정점들의 정보 -> 업데이트(경유할 때 더 최소비용일 경우) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 ..

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..