문제를 읽고 DFS와 BFS를 이용하는 문제라는 걸 알았다. 그래서 인접 행렬까지는 구현했는데 그 다음에 어떻게 해야 할지 막막했다. 상하좌우로 탐색하는 방법을 생각하는 게 꽤 오래 걸렸다. 일단은 DFS로 해결했는데 BFS로도 가능할 것 같다. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int m; static int n; // x, y 의 상하좌우 설정 static int[] dx = {1,-1,0,0}; static int[] dy = {0,0,1,-1}; s..

DFS와 BFS 기본을 연습할수 있는 문제였다. DFS는 많이 익숙해졌는데 BFS는 아직도 버벅거린다. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int n, m, v; static boolean[] visit; static StringBuilder sb; static StringTokenizer st; static int[][] arr; static int[] s; pu..

N과 M 2번 문제이다. 오름차순으로 정렬해야 하는 조건이 추가 되었다. idx를 추가해서 해결했는데 오히려 1번보다 간단하다고 느꼈다. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] arr; static int n, m; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new Bu..

문제 유형에 백트래킹이라고 나와 있었다. 백트래킹 기법중 DFS를 이용해서 문제를 풀었다. System.out.println(); 으로 매번 출력하는것보다 Stringbuilder를 이용해서 한번만 출력하는게 속도가 훨씬 빨랐다. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static boolean[] visit; static int[] arr; static StringBuilder sb = new StringBuilder(); public static void main(Str..

이 문제에 DP를 어떻게 적용할건지 고민이 많이 되었다. 지금 나는 DP 문제를 해결하는데 두 가지 큰 어려움이 있다. 1. DP를 사용하는것이 옳은지 판단하는것이다. 최적 부분 구조 : 문제를 나눌수 있어야 하고 나눈 문제들을 모아서 원래 문제를 해결할 수 있는 경우 중복 부분 문제 : 나눈 문제에서 동일한 계산을 계속 해야하는 경우 2. 문재를 읽으면서 점화식을 발견해야 한다. 문제가 1번 조건에 맞는지 생각을 한참 해봐야 하고, 점화식을 발견하기 위해 또 조금 고민해야 한다. 다양하게 DP 관련된 문제들을 계속 풀어봐야겠다. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;..

문제의 그래프를 보고 DFS / BFS를 이용하는 문제라고 생각했다. 먼저 DFS로 풀었는데 탐색경로 배열을 어떻게 해야 할지 잘 떠오르지 않아 한참을 고민했다. 탐색 경로 배열을 만들고 나니 DFS는 어렵지 않았다. BFS는 이번에 처음 풀어봤는데 생각보다 재밌었다. DFS는 깊이를 우선적으로 탐색해서 BFS는 너비를 우선적으로 탐색한다고 알고는 있었지만 직접 몇 문제를 풀어보지 않아서 이해가 덜 갔던 것 같다. 그리 어렵지 않은 문제임에도 몇시간동안 입력값이 주어지면 어떤 흐름으로 가는지 생각하니 확실히 이해가 간다. 모든 정점을 탐색한다면 DFS와 BFS 모두 사용해도 괜찮을 것이고 그래프의 크기가 아주 크거나 경로의 특징이 들어있다면 DFS를 고려하고 최단거리 문제라면 BFS를 먼저 생각할 것 같..

그리디 알고리즘을 이용하는 문제이다. 먼저 가장 큰 단위의 동전으로 낼 수 있을 만큼 내고 다음 동전의 단위로 넘어가서 또 낼수 있을 만큼 내면 된다. 이렇게 k의 값을 줄여나가다 보면 필요한 동전의 최소 개수가 나오게 된다. 예전에 그리디 알고리즘을 처음 접했을때 비슷한 문제를 풀어봤던 기억이 나서 쉽게 풀었다. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Collections; import java.util.StringTokenizer; public class Main { public static..

문제 유형부터 DP를 이용하라고 나와 있었다. 저번처럼 Top-down 방식과 Bottom-up 방식 모두를 생각해서 풀었다. 나는 Top-down 방식이 먼저 떠올랐고 재귀를 통해 성공했다. 오히려 점화식을 도출해야 풀 수 있는 Bottom-up 방식이 더 어려웠다. Top-down 방식은 n의 조건이 최대 10이기 때문에 성공한 것 같다. 아마 n의 크기가 컸다면 재귀 호출이 많아져서 시간 초과가 났을것 같다. Bottom-up 방식에서는 동적으로 배열의 크기를 설정했는데 런타임 에러가 나서 초기값을 11로 고정해서 풀었다. Top-down 방식 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStrea..

문제 설명에 힌트가 이미 나와 있었다. 앞사람의 시간이 적어야 총 걸리는 시간이 최소일 것이다. 따라서 P배열을 오름차순으로 정렬하여 더하면 최소 시간이 된다. 간단한 문제였다. 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.pars..