동적 계획법
-
[문제해결을 위한 창의적 알고리즘] 격자길 (고급, p163)알고리즘 2017. 2. 3. 17:54
이 문제는 0,0부터 n,m까지 갈 수 있는 길의 방법을 구하는 문제이다. 이전 포스트의 광석 수집 문제와도 비슷해 보인다. 한가지 신경쓸 점은 0,0부터 n,m까지 잇는 선보다 위쪽에 있는 점은 거쳐갈 수 없다는 점이다. 다이내믹 테이블이 채워지는 과정을 보면 더 이해가 쉬울 것같다. import java.util.Scanner; public class Crossway163 { public static int n, m; public static int[][] dt = new int[101][101]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); ..
-
[문제해결을 위한 창의적 알고리즘] 거스름돈 (고급, p156)알고리즘 2017. 2. 2. 13:30
거스름돈 문제는 중급에서도 다루었던 문제이다. 그러나 여기에서는 더 큰 숫자에 대해서 처리할 수 있도록 동적 계획법 (Dynamic Programming)으로 푸는 방법을 살펴보도록 하겠다. 아이디어는 1부터 주어진 금액까지의 배열을 만들고 각 동전으로 만들 수 있는 금액들을 만들어 보면서 동전이 가장 작은 숫자로 업데이트하는 방식이다. 해설에 설명된 것보다 좀 더 직관적으로 이해할 수 있는 방법으로 구현해 보았다. import java.util.Scanner; public class Change156 { public static int[] money = new int[10001]; public static void main(String[] args){ int m; int n; int[] coins = ..
-
[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, p149)알고리즘 2017. 2. 2. 12:22
이 문제는 앞선 포스트에서도 재귀적 방법으로 풀어 본적이 있는 문제이다. 그러나 숫자가 커짐에 따라 기하급수적으로 계산량이 늘어날 수 있으므로, 여기서는 가장 효율적인 방법으로 접근해 보려고 한다. 책에서도 점화식을 n, n-1, n-2 사이의 관계와 n과 n/2사이의 관계를 설명하고 있다. 지금까지 문제 풀이 방법으로 보았을때, 상향식 동적 계획법 (Dynamic Programming)이 가장 빠른 접근 방법이나 책에서는 보여주지 않고 있다. 따라서 이 방법을 풀이해 보고자 한다. 중요한 것은 점화식을 유도해 내는 과정을 잘 이해하는 것이라고 생각된다. 1) n이 짝수이면, 절반씩 나눠 채우는 방법과 1칸씩을 내어논 상태에서 채운 다음 2칸을 채울 수 있는 2가지 방법을 곱한다. 2) n이 홀수이면, ..
-
[문제해결을 위한 창의적 알고리즘] 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 =..
-
[문제해결을 위한 창의적 알고리즘] 색상환 2 (고급, p131)알고리즘 2017. 2. 1. 09:56
이전 포스트에서는 가장 기초적(?)인 방법을 소개했는데 이번에는 책에서 설명하는 방법 중 가장 효율적인 방법을 적어보고자 한다. 사실 점화식을 유도해 내는 과정이 좀 어렵게 느껴져서 그렇지 이전의 방법으로 문제를 풀 수 있었다면, 동적 계획법 (dynamic programming)으로 바꿔서 푸는 것은 그렇게 어려워 보이지 않는다. n개 색상중 k개를 뽑는 방법은 k가 1이면 n이라는 것과 k가 n/2를 넘으면 0이라는 것, 그외의 경우에는 n-2에서 k-1개를 선택하는 것과 n-1개에서 k개를 선택하는 것을 더하면 된다는 것을 유도해 내는 것이 중요하다. import java.util.Scanner; public class ColorCircleSol138 { public static final int ..
-
[문제해결을 위한 창의적 알고리즘] 잭과 콩나물 (고급 p.118)알고리즘 2017. 1. 30. 10:08
이 문제는 3중 중첩 for문을 사용하여 문제를 해결하고 있다. 문제 설명이 좀 아쉬운 점은, 주어진 m개의 가로 콩나물 외에 가로 콩나물을 더 추가할 수 있는데 주어진 2개의 콩나물 사이에 얼마든지 추가할 수 있다는 점이다. 즉, m개의 가로 콩나물이 1의 간격으로 주어지지만 추가하는 콩나물은 1 간격 사이에 얼마든지 추가할 수 있다. 비슷한 형태로 Floyd-Warshall (all pairs shortest path) 알고리즘도 참고해 보면 좋을 것 같다. import java.util.Scanner; public class JackAndBeanStalkSol123 { public static int n, m; public static int[] p=new int[501]; public static..
-
[문제해결을 위한 창의적 알고리즘] 앱 (고급 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 정답:..