JAVA Developer Training

완전 탐색문제 우리가 생각해야할 단계는 1. 벽을 3개 세우고 2. 바이러스를 퍼트린다 3. 안전구역의 갯수를 세어 제일 큰값을 도출한다 가 되겠다 각 단계들을 시행하기 위해서는 전제되어야 할점이 있는데 1. 데스나이트 문제와 같이 위치를 특정해줄 Node 객체가 있어야 한다는점 2. 바이러스를 퍼트리는 작업이후 다시 처음 맵으로 돌려서 반복하기 때문에 처음 맵으로 돌리기 위한 복사 과정이 있어야한다는 점 Node 객체 static class Node { int x, y; public Node(int x, int y) { this.x = x; this.y = y; } } x와 y 위치를 가지는 Node객체를 생성 입력 import java.util.*; import java.io.*; static int..

최소 발걸음 횟수, 최소 이동횟수 와 같은문제들은 DFS(깊이 우선 탐색)보단 BFS(너비 우선 탐색)가 확실한 것같다 체스판의 나이트 말의 이동궤적? 방향? 횟수를 찾는 문제이다. 때문에 처음부터 보자마자 이중배열을 이용하여 풀어야 겠다는 생각을했다. 우리가 고려해야 할 것은 1. 체스판의 상황[boolean], 크기 2. 나이트 체스말의 위치[x,y], 이동 정도가 있겠다 가장먼저 체스말, 객체를 만들어보자 class knight { int x; int y; int move; knight(int x, int y, int move){ this.x = x; this.y = y; this.move = move; } } x축을 이동할 int x y축을 이동할 int y 그리고 이동횟수 move를 담는 나이트..

주사위를 굴려 도착한 칸이 사다리면 사다리를 이용해 올라가고 뱀이 있는 칸이면 뱀을 따라서 내려간다. 이동하기 때문에 배열로 저장한다 또한 방문했던 칸은 다시방문하지 못하도록 boolean 배열을 사용해 막는다 - EX) 3 -> 9 -> 12 -> 8 -> 9 -> 12 ->..... 와 같은 식으로 무한히 빠져버릴 수 있기 때문 주사위의 눈은 1~6으로 앞의 6칸으로 이동할 수 있다. 6가지의 경우의 수를 모두 돌리는데 이때 도착지점이 사다리나 뱀일경우 해당 지점으로 이동하며 아니면 주사위의 눈만큼 위치를 이동시킨다. 이후 100에 도달했을때의 주사위 굴린 수를 호출한다. 이를 bfs로 코드로 만들어보자 설명은 주석으로 하겠다 static void bfs(){ Queue queue = new Link..

예제를 만들어 보는게 좋다고 생각한다 2 GBDDA CDEFHI 라는 예시가 있다는 가정하에 풀어본다면 10000* G + 1000*B + 100*D + 10*D + 1*A + 100000*C + 10000+D + 1000*E + 100*F + 10*H+ 1*I로 G B D D A 10000 1000 100 10 1 C D E F H I 100000 10000 1000 100 10 1 알파벳 자릿수 C 100000 D 10100 G 10000 B 1000 E 1000 F 100 H 10 A 1 I 1 가 된다. 위와같은 순서에서 높은 숫자를 자릿수가 큰 순으로 하나씩 배정해준다면 가장높은 결과값이 나오게 될 것이다. 알파벳들에 자릿수를 입력해주는 코드 for (int i = 0; i < n; i++) {..

고려해야할점은 1. 주어진 수의 순서를 바꾸면 안된다는것 2. 연산자 우선순위를 무시한다는것 3. 음수를 양수로 나눌때는 양수로 바꾸어 몫을 취하고 그 몫을 음수로 바꾸어준다는 것 ex) -8 / 4 => 8 / 4 => 2 => -2 + 식의 결과는 정수의 범위를 벗어나지않는다 ( +- 10억 ) 문제에서 주어지는 것 N개의 수 N-1개의 연산자 구해야 하는것 식의 최대값 최소값 피연자인 숫자는 위치가 고정되고 연산자의 위치만 바꿀수 있다 입력한 수들과 연산자들의 개수를 입력 해주면 모든 경우의 수를 탐색한뒤 가장 큰값과 가장 작은 값을 찾는 문제 DFS(깊이 우선 탐색)기법을 이용하여 전체 경우의 수를 탐색한다. int[] number;// 숫자 int[] operator;// 연산자 개수 publi..

문제에서 조심해야할 점은 바이토닉 부분 수열 이라는 점이다 바이토닉 수열이 아니라는것 바이토닉 수열에서 바이토닉은 특정값을 기준으로 왼쪽은 오름차순, 오른쪽은 내림차순인 수열을 말한다 문제에서 말하는 수열은 바이토닉 부분 수열은 힌트에서도 볼 수 있다 싶이 { 1 5 2 1 4 3 4 5 2 1 } 이렇다고 볼 수 있는데 즉 굵게 칠해진 부분이 바이토닉 부분 수열이고 그 중간에 끼는 5 1 4와 같이 흐름에 맞지않는 수는 빼고 개수를 세면 된다는 것이다. 이때 계산해야할점은 앞에서 올라가는 수와 뒤에서 올라오는 수를 더한값이 가장 큰것을 찾아야한다는점인데 이말인 즉, 앞에서 올라가는 수열의 최대값 과 뒤에서 올라가는수열의 최대값을 더해야한다는 것이다. 표로보면 아래와같다 입력수열 바이토닉 값 1 1 1 ..

여타 다른 DP문제들 처럼 1부터 차근차근 실행해보며 규칙을 찾아봤다 N이 1일땐 3x1 크기의 벽 경우의수 0 N이 2일땐 3x2 크기의 벽 경우의수 3 N이 3일땐 3x3 크기의 벽 경우의수 0 N이 4일땐 3x4 크기의 벽 경우의수는 3x2의 벽이 2개가 붙어있다고 생각하면 편하다 그러면 9가지 경우의 수에 추가적으로 이런 특수한 형태 2가지가 생겨 총 11가지의 경우의 수가 생긴다 N이 5일땐 3x5 크기의 벽 경우의수 0 N이 6일땐 3x6 크기의 벽 경우의 수는 1.3x4의벽 과 3x2의벽 2.3x2의벽 과 3x4의벽 3.3x6의 벽으로 나눌수 있겠는데 1번의 경우에는 3x4의벽의 가지수인 DP[4]와 3x2의벽의 가지수인 DP[2]를 곱해주면 11x3 = 33가지의 경우의 수 2번의 경우에도..

문제만보면 알아보기 힘들었던 문제 다이나믹 프로그래밍 문제가 다 그렇듯이 초반 작은 문제 몇번을 손으로 반복하면 규칙이보인다. N(만들어야하는 수) K(사용가능한 갯수) N=1 일때 K=1 이면 1 - 1개 K=2 이면 (1+0),(0+1) -2개 K=3 이면 (1+0+0),(0+1+0),(0+0+1) -3개 N=2 일때 K=1 이면 2 - 1개 K=2 이면 (2+0),(1+1),(0+2) - 3개 K=3 이면 (1+1+0),(1+0+1),(0+1+1),(2+0+0),(0+2+0),(0+0+2) - 6개 N=3 일때 K=1 이면 3 - 1개 K=2 이면 (0+3),(1+2),(2+1),(3+0) - 4개 K=3 이면 (0+0+3),(0+1+2),(0+2+1),(0+3+0),(1+0+2),(1+1+1),(..