다이나믹 프로그래밍
-
[문제해결을 위한 창의적 알고리즘] Maximum Sum (고급, p144)알고리즘 2017. 2. 1. 20:08
이 문제는 수열이 주어졌을때, 연속된 부분 수열의 합이 최대가 되는 값을 찾아 내는 문제이다. O(n^2)을 원하는 문제가 아니므로 점화식을 찾아내어 동적 계획법 (Dynamic Programming)으로 풀어야 하는 문제이다. 해설에서 잘 설명하고 있지만, k번째 항목으로 끝나는 부분 수열을 만든다고 하면, k-1번째까지의 최대 합에 k번째 값을 더한 값과 k-1번째까지의 합은 버리고 k번째 항목을 비교하여 둘 중 더 큰 값을 취하면 k번째 항목으로 끝나는 부분 수열의 최대값을 구할 수 있다. import java.util.Scanner; public class MaxSumSol148 { public static final int INF = 987654321; public static int[] S =..
-
[문제해결을 위한 창의적 알고리즘] 앱 (고급 p.112)알고리즘 2017. 1. 28. 18:31
이 문제는 배낭 문제와 비슷해 보이지만, 메모리 제약상 테이블을 크게 만들 수 없는 경우 어떻게 해결할 수 있는지 보여주는 문제이다. 해설에 자세하게 설명되어 있으므로 추가적인 설명은 생략하기로 한다. 다이나믹 테이블을 어떻게 채워나가는지 보면 보다 이해가 쉬울 것 같다. import java.util.Scanner; public class App112 { public static int n;public static int M;public static int[] mem = new int[101];public static int[] cost = new int[101];public static int[][] dt = new int[101][10001];public static int max(int a, in..
-
[문제해결을 위한 창의적 알고리즘] 배낭 문제 (고급 p.107)알고리즘 2017. 1. 28. 12:30
책에도 설명되어 있듯이 이 문제는 굉장히 잘 알려진 문제이다. 그러나, 처음 접하는 사람들에게 특히 동적 계획법 (Dynamic Programming)으로 푸는 방법은 낯설게 느껴질 수 있다. 책에 굉장히 깔끔하고 간결한 풀이가 소개되어 있어서 그 코드를 자바로 작성해 보았다. 약간 해설이 부족한 점이 있는 것 같아 보충 설명을 더하였다. DT[i][j]의 정의 1) i는 물건 번호 2) j는 주어진 무게 3) DT[i][j]는 i번째까지 물건까지 고려했을 때 (풀이에서는 n번째부터 거꾸로 계산하고 있음 유의), j 무게가 남아 있다면 가질 수 있는 최대 가치 풀이와 더불어 실제 테이블에 어떤 값이 쓰여지고 있는지 보면 이해가 좀 더 쉬울 것 같다. 예제 입력: 4 5 2 3 1 2 3 3 2 2 정답:..