Algorithm/Baekjoon
[백준] 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..
[백준] 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..
[백준] 3980 선발 명단 - Java
[백준] 3980 선발 명단 - Java
2022.08.17재귀의 basis 조건은 11명을 모두 뽑았을 때이다. 선수의 능력치가 0이 아니면 뽑고, 백트래킹을 돌려서 모든 경우를 탐색하자. 백트래킹은 정말 많이 풀어봐야 한다. 개념은 알지만 활용하는게 쉽지 않은 단원.. import java.util.*; import java.io.*; import java.math.*; public class Main { static int TC; static int[][] map; static boolean[] visit; static int ans; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { BufferedReader br = ..
[백준] 1325 효율적인 해킹 - Java
[백준] 1325 효율적인 해킹 - Java
2022.08.14시간 제한이 좀 까다롭다. 최대한 시간을 줄여야 한다. bfs로 작성했는데.. 그냥 출력하면 시간초과가 발생한다. StringBuilder로 출력을 최대한 줄여야 한다. import java.util.*; import java.io.*; import java.math.*; public class Main { static ArrayList[] list; static int N, M; static int max = 0; static ArrayList ans_list = new ArrayList(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader..