Map에 입력값을 넣고 key에 맞는 value 값만 출력하면 되는 문제다. 입출력 값이 길어지면 시간 초과가 날수도 있겠다는 생각을 해서 BufferedWriter를 사용했다. 아주 간단하고 쉬운 문제였다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception{ BufferedReade..

1012 - 유기농 배추와 비슷한 문제였다. DFS를 이용해서 풀었는데 결과가 계속 틀렸다고 나왔다. 맞왜틀을 30분이나 하고서는 문제에서 출력을 오름차순으로 하라는 것을 발견했다... 정렬되게 수정하고 다시 제출해도 또 틀렸다고 나오길래 1시간을 고민했다. 문제는 visit 배열을 사용하지 않아서 하나의 단지에서 하나의 아파트만 있다면 0으로 리턴되는 것이 문제였다. visit 배열을 안 쓰고 답을 내고 싶어서 고민하다가 탐색한 집은 0으로 바꾸고 좌표를 이동시키고 재귀호출을 하면 정답이 되는 것을 발견했다. 다음부터는 그냥 visit 배열을 사용해서 풀어야겠다... 최종 코드 import java.io.BufferedReader; import java.io.IOException; import java..

문제를 읽고 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..