동적계획법
수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 기본 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. -위키백과
조금더 쉽게 설명하자면 작은 문제들을 해결한다음에 이 해결한 결과들을 바탕으로 보다 더큰 문제의 해답을 얻는 방법이다.
(작은 문제들의 해를 배열에 저장한 다음 그것들을 순환적인 성질을 이용하여 결합해 큰 문제의 해를 구하는 것)
동적계획법의 특징은 다음과 같다.
1.동적계획법은 해를 저장하는 배열을 사용한다 ( Table)
동적계획법이 분할정복( Divide and conquer : 큰 문제의 해를 쪼개 작은 문제의 해를 구하는 방식)과 구별되는 가장 큰 특징이다.
배열을 이용하면 똑같은 문제의 해를 여러번 구할 필요없이 Table에서 꺼내서 사용할 수 있다.
2. 동적계획법은 순환적인 성질을 이용한다.
동적계획법에서는 점화식 이라는 것을 사용한다. 이점화식은 큰 문제와 작은 문제간의 관계를 나타내는 식이다
큰 문제를 풀기 위해 작은 문제의 대한 해답을 미리 구해놓아야 된다는 뜻이다.
동적계획법이 확실히 유용한 알고리즘 설계기법이긴 하지만 어떤 문제에든지 적용할 수 있는 것은 아니다.
동적계획법이 성립하기 위해서는 최적화 원리가 성립해야 한다.
최적화 원리란?
한 문제에 대한 해가 최적이면 그 문제를 이루는 부분 문제들의 해도 최적이다.(뒤에 문제에서 더자세히 알아보자)
동적계획법 문제를 풀기 위해 다음과 같은 사항들을 고려해야 한다.
1. 문제가 최적화의 원리가 성립하는지 검사(즉 동적 계획법으로 해결할 수 있는지)
2. 부분문제를 정의한다.
3. 우리가 구해야 하는 큰 문제는 어떻게 정의되는지 알아본다.
4. 큰 문제와 작은 문제간의 관계를 찾는다. 즉, 점화식을 구한다.
5. 점화식을 통해 작은 문제들을 어떤 순서로 구해 나갈 것인지를 결정한다.
6. 답을 얻는 과정을 추적하는 방법을 세워야 한다.
다음과 같이 개념만 알았을 때 이해가 잘 안갈수 가 있다. 실제 문제를 풀면서 알아보자.
[기업투자]
http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1098&sca=50&sfl=wr_subject&stx=%EA%B8%B0%EC%97%85%ED%88%AC%EC%9E%90&sop=and
Time Limit : 1000MS (url 에서 문제 참조) 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려주다. 돈을 투자하지 않은 경우는 당연히 얻게 되는 이익도 없다. 예를 들어서, 한 투자가가 4만원을 갖고 두 개의 기업들에 각각 만원 단위로 투자했을 경우 얻을 수 있는 이익은 다음과 같다. 위의 경우 만일, 기업 A에 1만원, 기업 B에 3만원을 투자하는 경우 투자가가 얻는 이익은 14만원(5만원+9만원)이다. 4만원을 투자해서 가장 많은 이익을 얻을 경우 기업 B에만 4만원을 투자하는 경우로서 이때의 이익은 15만원이다. 여기서 투자가는 한 기업에 돈을 나누어 투자할 수는 없다. 투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 경우에 얻게 되는 이익이 주어졌을 때 가장 많은 이익을 얻을 수 있는 투자방식과 이때의 이익금을 구하는 프로그램을 작성하라. 첫 줄은 투자 금액과 투자 가능한 기업들의 개수이며, 둘때 줄부터 각 줄은 투자액수 및 각 기업이 투자가에게 주는 이익이다. 단, 총 투자금액은 300만원을 넘지 않으며, 투자 가능한 기업의 개수는 최대 20개이다. 첫 줄에 얻을 수 있는 최대 이익을 출력하고, 둘째 줄에는 각 기업에 투자한 액수를 출력한다. 입력 예 4 2 1 5 1 2 6 5 3 7 9 4 10 15 출력 예 15 0 4
|
다음은 기업투자 문제이다. 정올 올림피아드 문제인제, 동적계획법의 기법을 적용하지 않으면 도저히 풀 수 없는 문제이다.
다음 문제를 동적계획법을 적용시켜 풀어보자.
다음문제는 제한된 투자금액을 가지고 여러개의 기업에 어떻게 나눠서 투자해야지 가장 최고의 투자효율을 얻을 수 있는지에 대한 문제이다.
여기서 우리가 처음에 알 수 있는 것은 해결해야될 큰 문제이다.
큰문제는 F[i,j] = 1~i 개의 기업에 j원을 투자 했을 때의 최대 이익 이다.
인제 우리는 이러한 큰 문제를 해결하기 위해서 문제를 작은 문제로 나누어야 한다.
이 나누는 것이 가장 어렵다.
일단 문제를 나눠서 1개의 기업에만 투자를 한다고 생각해보자.
1개의 기업에 0만원을 투자했을 때 얻을 수 있는 최대이익? 0만원 F[1,0]= 0
1개의 기업에 1만원을 투자 했을 때 얻을 수 있는 최대이익? 5만원 F[1,1]= 5
1개의 기업에 2만원을 투자 했을 때 얻을 수 있는 최대 이익? 6만원 F[1,2]=6
1개의 기업에 3만원을 투자 했을 때 얻을 수 있는 최대 이익? 7만원 F[1,3]=7
1개의 기업에 4만원을 투자 했을 때 얻을 수 있는 최대 이익? 8만원 F[1,4]=8
1개의 기업에 4만원을 투자했을 때 이익은 우리는 표를 이용해서 쉽게 알 수 있다.
그럼인제 2개의 기업을 생각해보자.
2개의 기업에 1만원을 투자했을 때 얻을 수 있는 최대이익?
이것을 구하기 전에 우리는 이전에 1개의 기업에 1만원 투자했을 때 의 최대이익을 알고 있다.
F[1,1]=5
지금우리가 구하고자하는 것은 2개의 기업에 1억을 투자했을때 F[2,1]=? 이다
1개의 기업이 1억을 투자했을 때의 해를 알고 있으니 2번째 기업에 1만원 투자했을때 (이익 1만원)이랑 비교해보면
우리는 F[2,1]=5라는 것을 알 수 있다.
그럼 인제 2개의 기업에 2만원을 투자 했을때 얻을 수 있는 최대이익을 생각해보자 F[2,2]=?
1개의 기업에 0만원을 투자하고 2번째기업에 2만원을 투자하는 경우 5만원 F[1,0]=0 C[2,2]=5 (C[i,j] 는 i번째 기업에 j원을 투자했을 때 이익)
1개의 기업에 1만원을 투자하고 2번째 기업에 1만원을 투자하는 경우 6만원 F[1,1]=5 C[2,1]=1
1개의 기업에 2만원을 투자하고 2번째 기업에 0만원을 투자하는 경우 6만원 F[1,2]=6 C[2,0]=0
3개의 경우를 비교해봤을때 2개의 기업에 2만원을 투자 했을 때 얻을 수 있는 최대이익는 6만원이라는걸 알 수 있다. F[2,2]=6
이런식으로 계속 계산할 경우 우리는 F[2,4]까지의 해를 구할 수 있다.
이를 점화식으로 나타내면
F[i,j] = Max {F[i-1,j-k] +C[i,k]} 단, 0<= k<=j) 로 나타낼 수 있다.
F[i,j] = 1~ i번째 기업까지 j만원을 투자 했을 때의 최대이익
C[i,j] = i번째 기업에 j만원을 투자 했을 때의 이익
우리가 방금 했던 F[2,2]를 다시 식으로 풀어보면
F[2,2]= F[1,2-k] +C[2,k] (0<=k<=j) 이다.
우리는 방금 위에서 k가 2만원일 때부터 0만원이 될때 까지 결과값을 봐서
F[2,2]=6이라는것을 알 수 있었다.
우리가 F[2,2]를 구하기 위해서 필요한 데이터는 1개까지의 기업에 0~2만원을 투자했을때의 최대이익 ,F[1,0~2] 이다.
해서 동적계획법에서 말하는 Table을 만들어서 작은 해의 값을 다 저장해 놔야 한다.
이런식으로 2번째 기업에 3만원 투자했을때 4만원 투자했을때 를 전부 구하면 F[2,4] = 2 개의기업에 4만원을 투자했을때의 최대이익까지 알 수 있다. 또 여기서 기업이 더추가된다면 우리는 두번째기업까지의 j액을 투자했을때 최대이익을 다 Table에 저장하고 있기때문에 추가된 3번째 기업의 1~4만원까지의 투자액만 알고 있다면 3번째기업까지 F[3,4] 완성할 수 있다.
최종 점화식은 F[i,j] = (if i=0) 0
(else) Max {F[i-1,j-k] +C[i,k]} 단, 0<= k<=j) 이다.
[java Code]
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Arrays; import java.util.Scanner; import java.util.Stack; public class Main{
static int N; static int K; static int[][] inv = new int[21][301]; static int[] com; static int[][] rate; static Stack<Integer> mount = new Stack<Integer>();
public static void main(String[] args) { try { System.setIn(new FileInputStream("res/inputInvest.txt")); } catch (FileNotFoundException e) { e.printStackTrace(); }
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); K = sc.nextInt();
com = new int[K+1]; rate = new int[K+1][N+1];
int curVal = 0; int idx; int maxVal = 0;
for (int i = 1; i <= N; i++) { idx = sc.nextInt(); for (int j = 1; j <= K; j++) { rate[j][idx] = sc.nextInt();
for (int k = 0; k <= i; k++) { int aVal = inv[j-1][i-k] + rate[j][k];
if(curVal < aVal) { curVal = aVal; // System.out.println("idx : " + j + " | K : " + k + " | curVal : " + curVal );
if(maxVal < curVal) { maxVal = curVal; } } } inv[j][idx]= curVal;
}
curVal = 0; }
System.out.println(maxVal);
findInv(K, N, maxVal);
while (!mount.isEmpty()) { System.out.print("" + mount.pop() + " "); }
}
private static void findInv(int co, int mo, int max) { if(co == 0) { return ; }
int k = 0; for (int i = 0; i <= mo; i++) { if(max == inv[co-1][mo-i] + rate[co][i]) { k = i; break; } }
mount.push(k);
int rest = inv[co-1][mo-k];
findInv(co-1, mo-k, rest); }
} |