IT 개발 돼지의 일상

출저 : https://www.acmicpc.net/problem/1783 "그리디 알고리즘, 내 머리속으로 계산." 여러 조건들이 있었다. 오른쪽으로만 이동하며, 이동 횟수가 4가 넘어가는 경우 가능한 4가지의 방법 모두 적어도 한번씩은 사용해야 한다. 이러한 부분들을 조건문으로 분기시킨다... 잘 생각해보자. n이 1,2,3,... 일때를 생각해보고, m이 7보다 작을때, 크거나 같을 때를 생각해보자. 12345678910111213141516171819202122232425import java.util.Scanner; public class Main { static int n,m; static Scanner sc = new Scanner(System.in); public static void mai..

출저 : https://www.acmicpc.net/problem/3055 "순서를 잘 생각한 BFS 두개." 먼저 물과 고슴도치를 이동 시키기 위해 두개의 Queue를 준비한다. 두개의 queue는 각 time 마다. 상하좌우로 이동할 것이다. 이때 물과 고슴도치 중 어떤 것을 먼저 움직여야 할까? 문제에 조건에 따르면 다음 시간에 물이 찰 곳에는 고슴도치가 이동하지 못한다고 했으므로, 물을 먼저 이동 시켜주고, 물이 찰 곳에 고슴도치가 이동하지 못하도록 해주어야 한다. (만약 고슴도치가 수영을 N 번 할 수 있다고 한다면 문제가 어려워 질거같다... ) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546..

출저 : https://www.acmicpc.net/problem/1937 "DP" DP를 이용한 문제이다. top down 방식을 사용한다. 재귀를 할 때, 리턴 값이 있는 경우 처리를 잘해 주어야 겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Main { s..

출저 : https://www.acmicpc.net/problem/3076 "구현" 더 좋은 게 있을듯...; 123456789101112131415161718192021222324252627282930313233343536373839import java.util.Scanner; class Main { static int R,C,A,B; static char[][] map; static StringBuilder sb = new StringBuilder(); public static void main (String[] args) { Scanner sc = new Scanner(System.in); R = sc.nextInt(); C = sc.nextInt(); A = sc.nextInt(); B = sc...

출저 : https://www.acmicpc.net/problem/2804 "구현" 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; class Main { static char[] A,B; static int N,M; static char[][] map; static int I,J; static StringBuilder sb = n..

출저 : https://www.acmicpc.net/problem/1890 "DP 와 2^63" 전형적인 DP 문제로서 Top-down 방식의 메모이제이션을 사용한다. Start 부터 시작해서 End 까지 탐색한다. 검색 중에 End 에 도착했다면 한 가지 방법이 있는 것이므로 1을 리턴하고 이 값은 함수를 호출한 dp[x] 에 누적된다. 아래 예를 보면 4,5,6 번 노드가 이와 같다. 이런식으로 "누적"을 하게 되면 해당 노드에서 End로 갈 수 있는 방법의 수가 dp[x]에 저장된다. DFS 나 BFS 로 풀면 시간초과가 날 것이 왜 dp를 쓰면 시간이 단축 되나? 라는 질문에 답은 7번 노드를 보면 된다. 7번 노드까지 탐색한 후에 6번 노드의 dp값을 체크하였더니 1이 저장되어 있더라. 6번 이..

출저 : https://www.acmicpc.net/problem/9291 "구현" 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static int T; static int[][] map; static boolean[] visited; static int[] d..

출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB "무식한 DFS" 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.Set;import java.util.StringTokenizer;p..

출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx "DFS와 가지치기" DFS를 이용해 해당 위치의 명령을 수행한다. 이 때, '?' 명령의 경우 4방향 dx,dy 에 대해 모두 탐색해 준다. 가능한 경우가 나왔을 때는 boolean 변수 find를 true 설정해주어 더이상 탐색하지 않도록 한다. 범위가 벗어날 경우 문제에서 제시한 예외처리를 해주는 것도 중요하다. 일일이 x,y 좌표가 범위를 벗어난 경우를 체크하자. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474..

출저 : https://www.acmicpc.net/problem/15486 "DP" 다시 보기. 12345678910111213141516171819202122232425262728293031323334353637383940import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static int n; static int[][] map; static int[] dp; public static void main(String[] args) throws IOException { BufferedReader br..