동적계획법
-
[문제해결을 위한 창의적 알고리즘] 두부 자르기2 (고급, p207)알고리즘 2017. 2. 24. 18:14
앞선 포스트에서는 완전 탐색으로 두부 자르기 문제를 푸는 방법에 대해 적어 보았다. 이번에는 동적 계획법으로 푸는 방법을 소개하고자 한다. 문제 해결을 위한 창의적 알고리즘 고급편의 가장 마지막에 있는 동적 계획법 문제이므로 난이도가 가장 높은 동적 계획법 문제로 보인다. import java.util.Scanner; public class TofuCutSol213 { public static int cu(){ return 1
-
[문제해결을 위한 창의적 알고리즘] Minimum Sum (고급, p200)알고리즘 2017. 2. 18. 23:09
이 문제는 비트 오퍼레이션을 통해 보다 빠르게 동작하는 방법을 알아보는 문제이다. 역시 동적계획법을 통해 문제를 푸는 방법을 알아본다. 비트 연산을 어떻게 적용하는지 알아두는 것이 핵심이라고 할 수 있겠다. import java.util.Scanner; public class MinSumSol205 { // 최대값 설정 public static final int INF = 987654321; // 입력 받을 공간 public static int[][] m = new int[21][21]; public static int bit, n; // 동적 테이블 선언 public static int[] DT = new int[1
-
[문제해결을 위한 창의적 알고리즘] 공주 구하기2 (고급, p191)알고리즘 2017. 2. 17. 17:07
앞선 포스트에서 메모이제이션 방법을 이용하여 푸는 방법을 적어보았다. 그러나 역시 동적계획법을 사용해야 성능이 보장된다고 할 수 있으므로, 이번에는 동적계획법 (Dynamic Programming) 방법을 이용해 푸는 방법을 알아보고자 한다. 책에는 오타가 있음을 유의한다. 아래에서 DT[a][b]=가는 다리오가 a의 위치 섬에, 오는 다리오가 b의 위치 섬에 있을 수 있는 모든 경우의 수라고 정의한다. import java.util.Scanner; public class SavePrincessSol197 { public static final int MOD = 1000;public static int n;// 풀이에서는 array size가 501로 선언되어 있으나 n이 3~20까지이므로 20이면 충분..
-
[문제해결을 위한 창의적 알고리즘] 선물 (고급, p178)알고리즘 2017. 2. 11. 20:29
이 문제도 이전에 중급에서도 등장했던 문제이다. 그러나 마찬가지로 동적계획법 (Dynamic Programming)으로 풀려고 하면 방법이 잘 생각나지 않는다. 특히 무게의 합을 가지고 다이나믹 테이블을 만든다는 점을 유의해서 풀어야 한다. 아래에서 DT[k][b][c]= 현재 k개의 선물을 받았을 때, 길순이가 부피 b, 길삼이가 부피 c를 받을 수 있으면 1, 그렇지 않으면 0으로 정의한다. import java.util.Scanner; public class PresentSol190 { public static int n, W;public static int[] G = new int[21];public static int A, B, C;public static int ans = 0x7fffffff;..
-
[문제해결을 위한 창의적 알고리즘] 돌다리 건너기 (고급, p178)알고리즘 2017. 2. 11. 20:05
이 문제는 중급편에서도 나왔던 문제인데, 동적계획법 (Dynamic Programming)으로 풀려고 하면 다이내믹 테이블을 생각해 내기 쉽지 않은 문제로 보인다. 다이내믹 테이블이 어떻게 만들어지는지 보면서 풀어보면 좋을 것 같다. 아래에서 'DT[s][r]=s돌다리에서 r번 문자로 끝나는 모든 경우'이다. import java.util.Scanner; public class StoneBridgeSol183 { public static char[] rol = new char[30];public static char[][] dol = new char[2][120];public static int[][] DT = new int[2][30];public static int rc;public static in..
-
[문제해결을 위한 창의적 알고리즘] 광석 수집 (고급 p.103)알고리즘 2017. 1. 27. 21:00
이 문제는 동적계획법 (Dynamic Programming)을 배울때, 가장 기본적인 유형으로 볼 수 있는 문제이다. 오른쪽과 아래쪽으로만으로 움직일 수 있다는 제약 조건 때문에, 왼쪽의 값과 위쪽의 값을 비교해 가면서 다이내믹 테이블을 업데이트하면서 답을 구해갈 수 있다. 나머지 설명은 책을 참고하면 되겠다. 책을 읽다 보니 한가지 수정했으면 하는 부분이 있는데 바로 106페이지의 T[i][j] 점화식에서 base case로 0 (i=0, j=0)이라고 되어 있는데, mine[0][0]으로 하는 것이 맞을 것 같다. import java.util.Scanner; public class Mining103 {public static int n;public static int m;// 책에서는 220까지 하..
-
[문제해결을 위한 창의적 알고리즘] 숙직 선생님 (고급 p.97)알고리즘 2017. 1. 26. 18:11
이 문제는 책에서 여러가지 형태로 다루고 있으므로, 추가적인 설명은 적지 않도록 하겠다. 가장 마지막 방법이 가장 효율적인 방법이므로, 그 방법을 나름의 방법으로 코딩해 보았다. 개인적으로는 책에 설명된 것보다 더 직관적인 코드라는 생각이 든다. 간략 설명 1) 현재 위치에서 3가지 능력 각각에 대해 갈 수 있는 위치를 업데이트 한다. 2) 해당 위치에 이미 업데이트 된 값이 있으면 작은 경우에만 업데이트 한다. 3) 만약 b의 위치가 지났다면 멈춘다. 4) b의 위치에 적혀 있는 값을 출력한다. import java.util.Scanner; public class DutyTeacher97 { // 선생님과 누군가의 위치 public static int a, b; // 3가지 능력 public stati..
-
[문제해결을 위한 창의적 알고리즘] Combination (고급 p.87)알고리즘 2017. 1. 21. 19:36
이 책의 앞부분에서 살펴본 문제 ([문제해결을 위한 창의적 알고리즘] Combination (고급, p29)) 동적 계획법 (Dynamic Programming)으로 해결해 보는 문제이다. ! (팩토리얼)을 빠르게 증가하므로 오버플로우를 내지 않고 계산하기 위해 이와 같은 방법으로 풀 수 있다고 한다. 여기서는 Dynamic Programming의 성능을 가장 최적화할 수 있는 상향식 풀이를 소개한다. (실제로 재귀함수를 이용한 하향식 접근 방법은 call stack이 오버헤드가 되어 성능이 좋지 않다). 문제에서 가장 중요한 것은 점화식을 유도하는 것인데, n개 중에서 k개를 고르는 방법은 1) n-1개에서 k개를 다 고르는 것과 2)n-1개에서 k-1개를 고르고 마지막 n번째 항목을 그냥 추가하는 방..