반응형 DP8 [백준] 2293번 - 동전 1 (Java) https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 동전의 종류가 n개 있다. k원이 되도록 하는 경우의 수를 구해야 한다. 동전의 수는 제한이 없다. 시간제한이 0.5초 이므로 이분탐색 혹은 DP일 가능성이 높다. 배열을 사용해서 동전의 가치를 저장한다. dp[i]는 i원까지 동전의 경우의 수이다. 10원을 표현하기 위해 동전 1, 2, 5를 갖고 있을 때 경우의 수는 점화식 dp[n] = dp[n-1] + dp[n-2] + dp[n-5] impo.. 2022. 10. 14. [백준] 2775번 - 부녀회장이 될테야 (Java) https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net * DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 - a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합 2) 점화식 찾기 - DP[k][n] = DP[k-1][1] + ... + DP[k-1][n] 3) 초기값 정하기 - DP[0][1] ~ DP[0][14]까지 호실 번호와 동일한 사람수를 가진다. DP 테이블을 2중 배열을 사용해서 세로축은 층수, 가로축은 호실.. 2022. 9. 28. [백준] 9095번 - 1,2,3 더하기 (Java) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 메모이제이션을 좀 안다고 생각했는데 한 방 먹은 문제다. 1시간 동안 고민했는데 풀지 못했다. 알고 봤더니 1~3까지 숫자를 계산할 때 약간의 상상력을 보태야 하는데 그까지 생각이 미치지가 못했다. * DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 2) 점화식 찾기 3) 초기값 정하기 1) DP 테이블 정의 - DP테이블은 1,2,3의 합으로 조합할 수 있는 경우의 수를 가진다. - 정수 n은 < 11이므로 DP[10+1]로 구성해서 값을 미리 구한 다.. 2022. 9. 28. [백준] 1003번 - 피보나치 함수 (Java) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. DP 테이블의 성격 정의 - DP[N][2]로 생성해서 DP[i][0]에는 0의 출력 횟수, DP[i][1]에는 1의 출력 횟수를 저장한다. - N 2022. 9. 27. [백준] 1463번 - 1로 만들기 (Java) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 2) 점화식 찾기 3) 초기값 정하기 1. 테이블 정의 DP[i] = 정수 i를 1로 만들때까지 걸리는 연산 횟수의 최소값 2. 점화식 찾기 DP[12]의 경우 a. 3으로 나눌 경우 -> DP[12] = DP[4] + 1 -> DP[x] = DP[x/3] + 1 b. 2로 나눌 경우 -> DP[12] = DP[6] + 1 -> DP[x] = DP[x/2] + 1 c. 1을 뺄경우 -> DP[12] = DP[11] + 1 .. 2022. 9. 26. 메모이제이션을 통한 동적 프로그래밍 동적 프로그래밍(dynamic programming)은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차다. 메모이제이션(memoization)은 하위 문제가 중첩될 때 재귀 호출을 감소시키는 간단하면서도 아주 뛰어난 기법이다. 본질적으로 메모이제이션은 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다. * 메모이제이션 구현 int fib(int n, int[] memo) { if (n == 0 || n == 1) return n; // memo 테이블을 확인해 fib(n)이 이미 계산된 건지 본다. if (memo[n] == 0) { // 값이 없으면 재귀호출 실행 memo[n] = fib(n-2, memo) + fib(n-1, memo); } return memo[n]; // 이미 계산된 값이 .. 2022. 9. 20. [백준] 2839번 - 설탕 배달 (Java) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 재귀나 반복문으로 푸는 문제가 아니다. 따라서 수들을 늘어서놓고 법칙을 찾아야 한다. N 3 4 5 6 7 8 9 10 11 12 봉지수 1 2 N / 5 1 2 N % 5 3 4 0 1 2 3 4 0 1 2 N 13 14 15 16 17 18 19 봉지수 3 N / 5 2 3 N % 5 3 4 0 1 2 3 4 1. 법칙성을 찾기 위해 N/5와 N%5의 값들을 구해본다. N 3 4 5 6 7 8 9 10 .. 2022. 9. 14. [백준] 1520번 - 내리막 길 (Java) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. map에는 높이 정보가 주어지고, 탐색은 상하좌우로만 가능하다. 2. 경로를 찾는데 높이가 지금보다 낮은 쪽으로만 이동 가능한 경로를 찾는다. 3. 가능한 경로의 개수를 찾는다. 4. dfs 파라메터로 좌표 정보를 넘겨준다. import java.util.*; /* [백준] 1520번 - 내리막 길 (Java) */ public class Main { int N, M; int A[][]; bool.. 2022. 9. 7. 이전 1 다음 반응형
