다이나믹 프로그래밍48 [백준] 2410: 2의 멱수의 합 - JAVA https://www.acmicpc.net/problem/2410 풀이dp문제. dp[0], dp[1]을 1로 초기화하고 dp배열을 채운다. dp[i] = dp[i-2] + dp[i/2] 의 점화식으로 진행한다. 메모리: 22032KB시간: 148ms언어: Java 11import java.io.*;public class Main { private static final int MOD = 1_000_000_000; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = I.. 2024. 5. 13. [백준] 15681: 트리와 쿼리 - JAVA https://www.acmicpc.net/problem/15681 풀이트리에 속한 간선의 정보가 주어지고, 루트의 번호가 주어진다. 트리의 정점을 포함해 자신보다 하위에 있는 정점들의 개수를 구하는 문제이다. 먼저 간선의 정보를 인접리스트에 담았다. 루트의 번호부터 dfs탐색을 통해 진행하는데 정점의 개수의 최대값이 크다보니 매번 구하면 시간 초과가 발생할 것 같았다. dp배열을 만들어 dfs탐색을 하며 dp에 저장하고 반환하는 식으로 구현했다. 메모리: 77800KB시간: 812ms 언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> tree; static int[] dp; stati.. 2024. 5. 13. [백준] 1005: ACM Craft - JAVA https://www.acmicpc.net/problem/1005 풀이위상정렬을 이용해 건물을 건설하는 시간을 구하는 문제. 어떤 건물을 짓기 위해 우선적으로 지어져야 할 건물이 있다. 특정 번호의 앞에 지어져야할 건물이 여러개가 있다면 그중 가장 오래걸리는 것이 끝난 후 지을 수 있게 된다. 따라서 걸리는 시간을 오름차순으로 하기 위해 우선순위큐를 이용했다. 목표한 건물에 도달했으면 시간을 출력하면 끝. 메모리: 245956KB시간: 864ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node implements Comparable { int num; int time; .. 2024. 5. 13. [백준] 1516: 게임 개발 - JAVA https://www.acmicpc.net/problem/1516 풀이위상 정렬을 이용하는 문제이다. 건물을 지을 때 먼저 지어야 할 건물이 정해져 있다. 즉, 먼저 지어야할 건물의 개수가 0이되면 지을 수 있는 것이다. 인접리스트로 건물을 지은 다음에 지을 수 있는 건물을 저장해놓는다. in_degree 배열에 먼저 지어야 할 건물의 개수를 저장한다. in_degree 배열이 0인 것부터 먼저 queue에 넣고 탐색하여 인접리스트에서 다음 건물의 in_degree값을 하나 빼준다. in_degree 값이 0이되면 queue에 넣는다. 메모리: 21612KB시간: 260ms언어: Java 11import java.io.*;import java.util.*;public class Main { pub.. 2024. 5. 13. [백준] 2565: 전깃줄 - JAVA https://www.acmicpc.net/problem/2565 풀이A와 B기둥에 전깃줄을 연결하는데 서로 겹치는 전깃줄이 없어야 한다. 입력을 받아 A기준으로 오름차순으로 정렬한다. 예제에서 정렬하면 A는 오름차순으로 정렬되고 B는 다음과 같이 된다. {8, 2, 9, 1, 4, 6, 7, 10} 전깃줄을 교차되지 않게 하기 위해 없애야 하는 최소의 개수를 구해야 한다. 즉, 가장 많이 연결이 되어야 한다는 의미이다. 정렬을 하니 주어진 배열에서 가장 긴 증가하는 부분수열(LIS)의 길이를 찾는 문제로 바뀌었다. LIS의 길이를 찾아 N에서 빼주면 없애야 할 전깃줄의 개수가 나온다. LIS를 찾는 방법은 DP를 이용한 방법과 이분 탐색을 이용한 방법이 있다. DP를 이용한 방법은 들어갈 수 있는 인덱.. 2024. 5. 13. [백준] 1937: 욕심쟁이 판다 - JAVA https://www.acmicpc.net/problem/1937 풀이특정 위치에서 시작하여 상하좌우로 움직일 수 있다. 현재 칸보다 숫자가 더 큰 칸으로만 갈 수 있는데 갈 수 있는 최대 칸 수를 구하는 문제. 처음에 dfs로 풀었는데 시간초과가 났다. 모든 칸을 봐야하는데 이미 기록된 칸은 더이상 볼 필요가 없었다. 메모이제이션을 하여 dp배열에 저장된 값이 있다면 그 값을 반환해주고 바로 끝내도록 했다. 메모리: 37148KB시간: 516ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n; static int[][] forest, dp; static int[][] vector = { { .. 2024. 5. 12. [백준] 9252: LCS 2 - JAVA https://www.acmicpc.net/problem/9252 풀이LCS(최장 공통 부분 수열)문제. 두 수열이 주어졌을 때 공통된 부분 수열 중 가장 긴 것을 찾는다. 점화식은 다음과 같다. dp[i][0], dp[0][j]는 0으로 채워진 상태로 시작한다.if (a[i - 1] == b[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1;} else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}수열A와 수열B를 한 글자씩 비교한다. 두 문자가 다르다면 dp[i-1][j]와 dp[i][j-1] 중 큰 값으로 하고, 같다면 dp[i-1][j-1] + 1 으로 한다. 이렇게 하면 최장 공통 부분 수열의 길이를 구할 수 있다.. 2024. 5. 12. [백준] 10942: 팰린드롬? - JAVA https://www.acmicpc.net/problem/10942 풀이수열이 주어지고 수열의 S번째 수부터 E번째 까지 팰린드롬을 이루는지 확인하는 문제. 수열의 1번부터 N번까지의 팰린드롬 여부를 담는 dp배열을 만든다. S, E를 입력받으면서 dp배열에 결과를 저장하면서 판별한다. 팰린드롬 판별은 재귀를 통해 구현했다. S와 E가 같으면 한 자리수이므로 true이고, 아닌 경우 다시 재귀를 통해 S+1과 E-1의 팰린드롬 여부를 판별하도록 했다. 메모리: 219448KB시간: 832ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[] arr; static boolean[][] dp; pub.. 2024. 5. 12. [백준] 20303: 할로윈의 양아치 - JAVA https://www.acmicpc.net/problem/20303 풀이dp와 분리집합을 이용하는 문제. 사탕을 최대로 뺏어야 하는 문제였다. 친구들로부터 사탕을 뺏는데, K명 미만으로부터 사탕을 빼앗아야 한다. 한 친구의 사탕을 뺏으면 그와 친구인 친구들의 사탕을 함께 뺏는다. 각 친구별로 사탕의 개수를 알고 있고, 누구와 친구 관계를 갖고있는지 주어진다. 따라서, 분리집합(union-find)을 이용해 친구별로 그룹을 만들어 그룹별로 몇 명인지 몇 개의 사탕을 가지고 있는지 저장한다. 저장된 자료를 통해 배낭문제 알고리즘을 적용하여 최대 K-1명일 때 최댓값을 구했다. 메모리: 875636KB시간: 1152ms언어: Java 11import java.io.*;import java.util.*;pub.. 2024. 5. 12. [백준] 23083: 꿀벌 승연이 - JAVA https://www.acmicpc.net/problem/23083 풀이경로의 개수를 세야 하는 DP문제. 벌집 구조이다. 아래쪽, 오른쪽 위, 오른쪽 아래 3가지 방향으로 이동할 수 있다. bottom-up으로 진행을 하면 오른쪽 위로 이동할 때 처리가 곤란할 것 같아서 top-down방식을 채택했다. dp배열의 초기값을 -1로 설정하고 -1이 아닌 경우에는 dp배열의 값이 설정되었다는 것이므로 dp배열의 값을 반환했다. 구멍뚫린 칸은 0으로, (1, 1)은 1로 설정했다. 현재 칸을 (r, c)라고 할때 c가 2의 배수인 경우와 아닌 경우 탐색 해야 하는 배열이 달랐다.if(c % 2 == 0) { return dp[r][c] = (doDp(r + 1, c - 1) + doDp(r, c - 1).. 2024. 5. 12. 이전 1 2 3 4 5 다음