Algorithm
N+1차원 dp
N+1차원 dp
2022.08.31N차원 배열만으로는 문제풀이에 부족한 경우가 생긴다. 이럴 때 N+1차원 배열을 사용해 dp를 적용할 수 있는데.. 아무래도 N차원 dp보다는 생각하기 쉽지 않다. 핵심은 N차원으로는 해결할 수 없으니 이차원으로 메모리를 확장하는 부분이다. 확장한 메모리를 어떻게 사용할 지는 문제마다 다르니, 역시 많이 풀어서 감을 잡는게 중요하다. https://www.acmicpc.net/problem/1495 boolean dp[i][j] = i번째 곡에서 j볼륨을 사용할 수 있는가? https://www.acmicpc.net/problem/14852 빠른 계산을 위해 이차원 배열을 도입해서 이 전까지의 값을 저장한다. https://www.acmicpc.net/problem/14722 dp[r][c][n] = r..
[백준] 20152 Game Addiction - Java
[백준] 20152 Game Addiction - Java
2022.08.28고등학교에서 확률과 통계를 배울 때 자주 볼 수 있는 유형이다. 대충 이런 유형으로 특정 경로를 가면 안되게 설정해놓거나 특정 방향으로만 가야 되는 제약을 걸어두고 최단 경로의 수를 구하는 문제.. 이 문제도 이전 결과를 사용하는 다이나믹 프로그래밍으로 해결할 수 있다. import java.util.*; import java.io.*; import java.math.*; public class Main { static StringBuilder sb = new StringBuilder(); static long[][] dp; static int H, N; public static void main(String[] args) throws Exception { BufferedReader br = new Bu..
[백준] 2876 그래픽스 퀴즈 - Java
[백준] 2876 그래픽스 퀴즈 - Java
2022.08.28문제를 잘 이해해야 한다. 두 책상을 고르고, 두 책상을 포함해서 그 사이에 있는 모든 책상에 대해서 퀴즈를 낸다. 이 때 책상 당 한명씩만 퀴즈를 내고, 퀴즈를 맞추는 학생들의 성적은 동일해야 한다. 즉, 같은 성적으로 연속되는 학생 수의 최댓값을 구하면 된다. 1 ~ 5 까지의 성적이 있으니 모두 구하고 최댓값을 출력하자. import java.util.*; import java.io.*; import java.math.*; public class Main { static StringBuilder sb = new StringBuilder(); static int[] dp; public static void main(String[] args) throws Exception { BufferedReader..
[백준] 21317 징검다리 건너기 - Java
[백준] 21317 징검다리 건너기 - Java
2022.08.26dp문제인줄 알았는데.. 그냥 백트래킹만 써도 시간 초과 없이 풀린다. 보통 백트래킹으로 시간 초과가 예상되면 dp + 백트래킹을 사용해 시간을 줄이는 방법을 사용한다. 이제 백트래킹은 어느정도 구현할 줄 아니까.. 아직 익숙하지 않은 dp 부분을 좀 더 공부해보자. import java.util.*; import java.io.*; import java.math.*; public class Main { static int ans, N, K; static Stone[] arr; static final int INF = 987654321; static int dp[]; static boolean bigbig; static StringBuilder sb = new StringBuilder(); public ..
[백준] 1106 호텔 - Java
[백준] 1106 호텔 - Java
2022.08.25dp[사용한 비용] = 최대로 늘어나는 고객 수... 로 dp 배열을 채워보자. dp[j] = Math.max(dp[j], dp[j - cost[i]] + effect[i]); 점화식은 위와 같다. 입력으로 들어오는 홍보 정보에 대해 dp 배열을 순회하면서, 효과가 더 커지는 경우 값을 갱신해준다. 즉, 입력으로 12 2 3 5 1 1 가 들어오면 dp 인덱스 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 dp 값 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 dp 값 0 1 2 5 6 7 10 11 12 15 16 17 20 21 22 25 26 27 이런 식으로 dp값이 갱신된다. import java.util.*; import java..
[백준] 9489 사촌 - Java
[백준] 9489 사촌 - Java
2022.08.24트리를 저장할 때 항상 리스트 배열과 행렬을 사용해야 하는 건 아니다. 위의 두 방법 말고도 배열 2개를 통해 해당 노드의 부모와 해당 노드의 값을 저장할 수 있다. 트리를 저장하는 방법은 문제에 따라 유동적으로 바꿔서 사용하자. (https://loosie.tistory.com/608 참고 블로그) import java.util.*; import java.io.*; import java.math.*; public class Main { static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new Inp..
백트래킹 정리
백트래킹 정리
2022.08.191 ~ N 중 M개를 뽑아야 한다. 1. 중복 없이 뽑아보자. for(int i=1; i
[백준] 2529 부등호 - Java
[백준] 2529 부등호 - Java
2022.08.19부등호 조건에 맞게 숫자를 넣어가며 백트래킹 돌리면 된다. 이 때 int 범위로는 값을 제대로 표현할 수 없으니 long 타입을 사용하자 (최대, 최소 설정에도 Long.MAX_VALUE) import java.util.*; import java.io.*; import java.math.*; public class Main { static int[] select; static char[] operators; static int N; static boolean[] visit; static long max = Long.MIN_VALUE; static long min = Long.MAX_VALUE; public static void main(String[] args) throws Exception { Buff..
[백준] 1553 도미노 찾기 - Java
[백준] 1553 도미노 찾기 - Java
2022.08.18왼쪽 상단부터 우측 하단까지 차례대로 탐색한다. 도미노를 놓을 수 있는 두 가지 방향으로 모두 놓아보면서 백트래킹을 돌리자. 여기서 행을 늘리면서 탐색할 때 주의하자. "왼쪽 상단부터 우측 하단" 방향으로 탐색해야 한다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int[][] map = new int[8][7]; static int[][] select = new int[8][7]; static boolean[][] visit = new boolean[8][7]; static boolean[][] domino = new boolean[7][7]; static int cnt = 0; public s..
[백준] 15658 연산자 끼워넣기 (2) - Java
[백준] 15658 연산자 끼워넣기 (2) - Java
2022.08.18백트래킹 연습하기 좋은 문제. 백트래킹의 기본형을 이해하고 나서는 활용에 집중하자. import java.util.*; import java.io.*; import java.math.*; public class Main { static int N; static int max = Integer.MIN_VALUE; static int min = Integer.MAX_VALUE; static boolean[] visit; static int[] nums; static int[] operators; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { BufferedReader ..
[백준] 17136 색종이 붙이기 - Java
[백준] 17136 색종이 붙이기 - Java
2022.08.17붙이는 개수가 최소가 돼야 한다. 크기가 큰 색종이부터 쓰면 최소 개수를 구할 수 있다. 스도쿠 문제를 풀 때 처럼 좌측 상단에서 우측 하단으로 내려가면서 탐색한다. 색종이로 덮는 작업과 덮은걸 치우는 작업은 따로 메서드로 만들어서 진행하자. 사용할 수 있는 색종이의 수가 정해짐에 유의하고 백트래킹을 돌리면 된다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int[][] map = new int[10][10]; static int ans = Integer.MAX_VALUE; static int[] remain = {0, 5, 5, 5, 5, 5}; static StringBuilder sb = n..
[백준] 6443 애너그램 - Java
[백준] 6443 애너그램 - Java
2022.08.17백트래킹으로 푸는데.. 중복 확인을 안하고 풀면 메모리가 터진다. visit 배열을 적절히 조작해 중복되는 경우를 줄여야 한다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int TC; static char[] select; static int[] visit; static char[] string; static int ans; static TreeSet ts = new TreeSet(); static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { BufferedReade..