[동적 계획법]
큰 문제를 해결하기 위해 작은 부분 문제로 분할한 뒤 하나의 부분 문제에 대한 해답을 구한다.
이후의 부분 문제에 대한 답을 구하기 위해서 이전에 구한 부분문제의 답을 참조한다. 이러한 과정을 진행할 때 이전에 해결한 부분문제를 참조해서 다음 부분문제의 답을 구할 수 있다.
이처럼 작은 부분문제들의 해를 먼저 구하여 저장하고 더 큰 문제의 해를 구할 때 작은 문제의 해를 반복 계산하지 않고 저장된 결과를 사용하는 것을 말한다.
이때 꼭 필요한 것이 점화식이다.
점화 식을 세우는 방법
1. 주어진 문제의 해를 구하기 위한 순환적인 성질을 표(1,2차원배열, 테이블)로 구성하여야 한다.
2. 전체 문제도 부분문제 형태로 표현할 수 있어야 한다. (큰 문제를 작은 문제로, 규칙성을 찾으면 가능하다.)
3. 문제를 어떻게 부분문제로 분할할 것인지 생각해야 한다.
4. 일반적으로 동적 계획법 문제는 일정 회수의 선택을 반복하는 구조로 이루어져 있다.(하나씩 하나씩..)
5. 그 상태에서의 선택과 그 선택 전의 상태를 고려하라.
6. 최적 해를 찾는 문제라면 그 가능성 중에서 가장 좋은 선택을 찾아라.
7. 답을 얻는 과정을 추적하는 방법을 설계해야 한다.
동적 계획법의 특성
1. 최적 결정의 순서가 초기상태와 결정이 무엇이든지 간에 나머지의 모든 결정들은 첫 번째에 나타난 상태에 관해서 최적결정 순서를 구성시키는 원칙을 지닌다.
2. 한번 어떤 부분문제가 해결되면 그 해를 기억함으로써 결코 두 번 다시 계산되지 않는다.
3. 모든 가능성에 대한 고려가 불충분할 경우 최적의 결과를 보장할 수 없다.
동적 계획법을 구현하기 위해서는 충분히 많은 가능성에 대한 고려를 해야 한다.
또한, 다른 방법론에 비해 많은 표(배열)을 이용하므로 메모리를 많이 요구한다.
주의: 한가지라도 잘못 구성하거나 계획하면 0점입니다.
1. 최대 부분 증가수열 문제
[문제]
n개의 자연수들이 주어졌을 때 그 중에서 가장 길게 증가하는 (작은 수에서 큰 수)원소들의 집합을 찾는 프로그램을 작성하라.
Input.txt
9
11 17 5 8 6 4 7 12 3
output.txt
4
[분석]
- 초기화
|
d[i]
|
11
|
17
|
5
|
8
|
6
|
4
|
7
|
12
|
3
|
|
c[i]
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
|
V[i]
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
-1
|
① {11, 17}의 숫자만 있다고 가정하고
② {11, 17, 5}의 숫자만 있다고 가정한다.
③ 하나씩 늘려가면서 최대값을 구한다.
④ 선택된 수와 이전의 수들과 비교하여 크면 c[i]를 1씩 증가시킨다.
|
d[i]
|
11
|
17
|
5
|
8
|
6
|
4
|
7
|
12
|
3
|
|
c[i]
|
1
|
2
|
1
|
2
|
2
|
1
|
3
|
4
|
3
|
|
v[i]
|
-1
|
1
|
-1
|
3
|
3
|
-1
|
5
|
7
|
-1
|
⑤추적한다.
2. 가방문제
[문제] 최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 물건들이 있다. 이 물건들의 가치는 각각 4,5,10,11,13이다. 이 물건을 가방에 담는데 17kg을 넘지 않으면서 최대의 가치가 되도록 하려면 어떤 조합으로 물건을 담아야 할까?(이때 물건들은 쪼갤 수 없다)
input.txt
3 4
4 5
7 10
8 11
9 13
output.txt
24
[분석]
1. 첫 번째 물건만 있다고 가정하면
|
i
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
|
c[]
|
0
|
0
|
4
|
4
|
4
|
8
|
8
|
8
|
12
|
12
|
12
|
16
|
16
|
16
|
20
|
20
|
20
|
|
b[]
|
-1
|
-1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
2. 모든 물건을 모두 적용하면
|
i
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
|
c[]
|
0
|
0
|
4
|
5
|
5
|
8
|
10
|
11
|
13
|
14
|
15
|
17
|
18
|
20
|
21
|
23
|
24
|
|
b[]
|
-1
|
-1
|
1
|
2
|
2
|
1
|
3
|
4
|
5
|
3
|
3
|
5
|
3
|
3
|
4
|
5
|
3
|
[점화식]
1) 적용한 물건을 저장한다. b[i] = j
2) 최고의 가치를 저장한다. c[i] = v[j] + c[i-s[j]]
[프로그램]
#include<stdio.h>
int n,k,i,a[100]={0,},b[100]={0,},j,d[100]={0,},f[100]={0,},pp;
int input()
{
FILE *ifp=fopen("input.txt","r");
fscanf(ifp,"%d %d",&n,&k);
for(i=1; i<=n; i++) fscanf(ifp,"%d %d",&a[i],&b[i]);
for(i=1; i<=n; i++){
d[i]=0;
f[i]=-1;
}
fclose(ifp);
return–-1;
}
int process()
{
for(i=1; i<=n; i++){
for(j=a[i]; j<=k; j++){
pp=d[j-a[i]]+b[i];
if(d[j]<pp){
d[j]=pp;
f[i]=i;
}
}
}
return–-1;
}
int output()
{
FILE *ofp=fopen("output.txt","w");
fprintf(ofp,"%d",d[k]);
fclose(ofp);
return–-1;
}
int main()
{
input();
process();
output();
return–-1;
}
3. 숫자 고르기
input.txt
7
3 1 1 5 5 4 6
output.txt
3
1 3 5
[분석]
① 입력파일에서 배열로 입력받는다.
|
D[]
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
F[]
|
3
|
1
|
1
|
5
|
5
|
4
|
6
|
② 이차원 배열에 입력한다.
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
1
|
|
|
1
|
|
|
|
|
|
2
|
1
|
|
|
|
|
|
|
|
3
|
1
|
|
|
|
|
|
|
|
4
|
|
|
|
|
1
|
|
|
|
5
|
|
|
|
|
1
|
|
|
|
6
|
|
|
|
1
|
|
|
|
|
7
|
|
|
|
|
|
1
|
|
③ 추적한 후 다시 처음으로 돌아오면 결과배열에 저장
131 (완성), 2131(x)
추적하는 동안 stack에 저장 비교 반복한다.
4. 동전교환문제
다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?
input.txt
15 4
50 12 5 1
output.txt
3 3 3
[분석]
1) 1원을 적용하면
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
c[]
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
t[]
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
2) 5원을 적용하면
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
c[]
|
1
|
2
|
3
|
4
|
1
|
2
|
3
|
4
|
5
|
2
|
3
|
4
|
5
|
6
|
3
|
|
t[]
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
3) 모든 동전을 적용하면
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
c[]
|
1
|
2
|
3
|
4
|
1
|
2
|
3
|
4
|
5
|
2
|
3
|
1
|
2
|
3
|
3
|
|
t[]
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
2
|
2
|
2
|
1
|
[점화식]
- 단위동전이 거스름 금액보다는 작아야 한다. (set[j]<i)
- 사용된 동전수가 현재 적용되는 단위 동전을 사용한 동전 수 보다 많으면 현재 적용되는 동전으로 바꿔야 한다.(c[i]>c[i-s[j]+1)
[프로그램]
#include<stdio.h>
int m,n,i,j,k[100]={0,},a[100]={0,},b[100]={0,},kk,hh;
int input()
{
FILE *ifp;
ifp=fopen("input.txt","r");
fscanf(ifp,"%d %d",&m,&n);
for(i=1; i<=n; i++){
fscanf(ifp,"%d",&k[i]);
}
a[0]=0;
for(i=1; i<=m; i++){
a[i]=999;
b[i]=-1;
}
fclose(ifp);
return–-1;
}
int process()
{
for(i=1; i<=n; i++){
for(j=k[i]; j<=m; j++){
kk=a[j-k[i]]+1;
if(a[j]>kk){
b[j]=i;
a[j]=kk;
}
}
}
return–-1;
}
int output()
{
FILE *ofp;
ofp=fopen("output.txt","w");
fprintf(ofp,"%d",a[m]);
fclose(ofp);
return–-1;
}
int main()
{
input();
process();
output();
return–-1;
}
5. 기계 만들기
[문제] 한 공장에서 동일한 제품 n개를 만들려고 한다. 이 제품을 만들 수 있는 서로 다른 기계가 m개가 있다고 하고, 각각의 기계에서 제품을 만드는데 사용되는 시간이 C1, C2, C3,,, Cm로 서로 다르다고 한다.
이때 n개를 생산하는데 들어가는 가장 작은 시간 값인 g를 구하는 프로그램을 작성하시오!
input.txt
5
3
1 3 4
output.txt
4
[점화식]
for(i=1; i<=9; i++){
k=1;
for(j=1; j<=0; j--){
if(use(j)+m(j) < use(k)+m(k)) k = j;
}
use[k] = use[k]+m[k];
}
6. 최대 공통 부분 문자열 찾기
두 개의 문자열이 다음과 같이 주어졌을 때 두 문자열의 부분 문자열 중
가장 긴 것을 구하시오
input.txt
a b c b d a b
b d c a b a
output.txt
4
[분석]
|
j
i
|
0
|
b
|
d
|
c
|
a
|
b
|
a
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
a
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
|
b
|
0
|
1
|
1
|
1
|
1
|
2
|
2
|
|
c
|
0
|
1
|
1
|
2
|
2
|
2
|
2
|
|
b
|
0
|
1
|
1
|
2
|
2
|
3
|
3
|
|
d
|
0
|
1
|
2
|
2
|
2
|
3
|
3
|
|
a
|
0
|
1
|
2
|
2
|
3
|
3
|
4
|
|
b
|
0
|
1
|
2
|
2
|
3
|
4
|
4
|
[점화식]
1) i=0 or j=0 d[i][j] = 0
2) a[i] = b[j] d[i][j] = d[i-1][j-1]+1
3) a[i] != b[j] d[i-1][j] >= d[i][j-1] d[i][j] = d[i-1][j]
d[i-1][j] < d[i][j-1] d[i][j] = d[i][j-1]
[프로그램]
#include<stdio.h>
#include<string.h>
int aa, bb, i, j;
char a[100]={0,},b[100]={0,}, d[100][100]={{0,},};
int input()
{
FILE *ifp=fopen("input.txt","r");
fscanf(ifp,"%s %s", a, b);
aa=strlen(a); bb=strlen(b);
for(i=1; i<=bb; i++){
for(j=1; j<=aa; j++){
if(b[i] == a[j]){
d[i][j]=d[i-1][j-1]+1;
}
else{
if(d[i-1][j] >= d[i][j-1]){
d[i][j]=d[i-1][j];
}else{
d[i][j]=d[i][j-1];
}
}
}
}
fclose(ifp);
return–-1;
}
int output()
{
FILE *ofp=fopen("output.txt","w");
fprintf(ofp,"%d",d[bb][aa]);
fclose(ofp);
return–-1;
}
int main()
{
input();
output();
return–-1;
}
7. 최소 편집 문제
두 문자열이 주어졌을 때 처음 문자열을 다음 문자열로 편집(삽입, 삭제, 대체)하여 바꾸려 한다.
이때 편집하는 횟수가 최소가 되도록 처리하는 프로그램을 작성하시오
input.txt
aabab
babb
output.txt
2
[분석]
|
j
i
|
0
|
b
|
a
|
b
|
b
|
|
0
|
0
|
1
|
2
|
3
|
4
|
|
a
|
1
|
1
|
1
|
2
|
3
|
|
a
|
2
|
2
|
1
|
2
|
3
|
|
b
|
3
|
2
|
2
|
1
|
2
|
|
a
|
4
|
3
|
2
|
2
|
2
|
|
b
|
5
|
4
|
3
|
2
|
2
|
[점화식]
1) i=0 d[i][j] = d[i][j-1]+1 (<- 삽입)
2) j=0 d[i][j] = d[i-1][j]+1 ( 삭제)
3) a[j]=b[i] d[i][j] = d[i-1][j-1] (그대로)
4) a[j] != b[i] 1) d[i-1][j] < d[j][j-1] => d[i][j] = d[i-1][j]+1 (삭제)
2) d[i-1][j] > d[i][j-1] => d[i][j] = d[i][j-1]+1 (삽입)
3) d[i-1][j] = d[i][j-1] => d[i][j] = d[i-1][j] (대체)
8. 가장 높은 탑 쌓기
[문제] 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.
(조건1) 벽돌은 회전시킬 수 없다.
(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
(조건3) 벽돌들의 높이는 같을 수도 있다.
(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌을 놓을 수 없다.
(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.
input.txt
5
2 3 4
4 4 8
9 2 3
16 2 5
1 5 2
output.txt
3
5 3 1
[분석]
1) 벽돌의 넓이 순서로 정렬
2) 최대값을 구한 후 추적
h[]
|
|
1
|
4
|
3
|
2
|
5
|
|
1
|
3 (-1)
|
|
|
|
|
|
4
|
|
2 (-1)
|
|
|
|
|
5
|
|
|
5 (1)
|
|
|
|
2
|
|
|
|
4 (-1)
|
|
|
5
|
|
|
|
|
10 (3)
|
그러므로 5 3 1 -1
[프로그램]
#include<stdio.h>
int ff[100]={0,},k[100]={0,},j,mm,i,n,d[100][100]={{0,},},kk,f[100]={0,},e[100]={0,};
int input()
{
FILE *ifp;
ifp=fopen("input.txt","r");
fscanf(ifp,"%d",&n);
for(i=1; i<=n; i++){
f[i]=i;
fscanf(ifp,"%d %d %d",&d[1][i],&d[2][i],&d[3][i]);
}
for(i=1; i<=n-1; i++){
for(j=i+1; j<=n; j++){
if(d[1][i] < d[1][j]){
f[0]=f[i];
f[i]=f[j];
f[j]=f[0];
mm=d[1][i];
d[1][i]=d[1][j];
d[1][j]=mm;
mm=d[2][i];
d[2][i]=d[2][j];
d[2][j]=mm;
mm=d[3][i];
d[3][i]=d[3][j];
d[3][j]=mm;
}
}
}
for(i=1; i<=n; i++){
k[i]=d[2][i];
ff[i]=0;
}
for(i=1; i<=n; i++){
if(d[2][i-1]<k[i]){
ff[i]=ff[i]+1;
e[i]=f[i];
}
}
for(i=1; i<=n; i++) kk=kk+ff[i];
fclose(ifp);
return–-1;
}
int output()
{
FILE *ofp=fopen("output.txt","w");
fprintf(ofp,"%d\n",kk);
for(i=n; i>=1; i--){
if(e[i] !=0){
if(i==kk+1){
fprintf(ofp,"%d\n",e[i]+1);
}else{
fprintf(ofp,"%d\n",e[i]);
}
}
}
fclose(ofp);
return–-1;
}
int main()
{
input();
output();
return–-1;
}
9. 기업 투자
[문제]
어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 않으면 당연히 얻게되는 이익도 없다.
input.txt
4 2
1 5 1
2 6 5
3 7 9
4 10 15
output.txt
0 4
15
[분석]
1) 먼저, 투자하는 기업이 없을 때 초기화
2)
|
|
0
|
1
|
2
|
|
0
|
0
|
|
|
|
1
|
0
|
|
|
|
2
|
0
|
|
|
|
3
|
0
|
|
|
|
4
|
0
|
|
|
다음 1번 기업까지만 있다고 가정하면
? 0번과 1번 기업 사이에서
투자액이 0만원이면 당연히 이익은 0이고
투자액이 1만원일 경우
① 0번à0원
1번à1만원
② 0번à1만원
1번à0원
①, ②번에서 ①은 0+5=5만원 이익, ②는 0+0=0만원 이익을 얻는다.
그러므로 최대값은 5만원이 된다.
같은 방법으로 2만원일 경우는 최대값은 6만원이 된다.
3) 2번 기업 까지 모두 적용하면
|
|
0
|
1
|
2
|
|
0
|
0
|
0
|
0
|
|
1
|
0
|
5
1
|
5(최대이익)
1(투자금액)
|
|
2
|
0
|
6
2
|
6
1
|
|
3
|
0
|
7
3
|
10
2
|
|
4
|
0
|
8
4
|
15
4
|
[점화식]
if(d[j][i] < d[k][i-1] + in[j-k][i]){
d[j][i] = d[k][i-1]+in[j-k][i];
in[j][i]=j-k;
}
[프로그램]
#include <stdio.h>
int max(int x, int y);
void follow();
int n, m;
int k;
int in_data[301][21];
int table[301][21], table2[301][21];
int fol[21];
void main()
{
FILE *in, *out;
in = fopen("input.txt", "r");
fscanf(in, "%d %d", &n, &m);
for(int i = 1; i <= n; i ++) {
int num;
fscanf(in, "%d", &num);
for(int j = 1; j <= m; j ++) {
fscanf(in, "%d", &in_data[num][j]);
table[num][j] = in_data[num][j];
}
}
fclose(in);
for(int j = 2; j <= m; j ++) {
for(int i = 1; i <= n; i ++) {
table[i][j] = max(i, j);
table2[i][j] = k;
}
for(i = 1; i <= n; i ++) {
in_data[i][j] = table[i][j];
}
}
out = fopen("output.txt", "w");
fprintf(out, "%d\n", table[n][m]);
follow();
for(i = m; i > 0; i --) {
fprintf(out, "%d ", fol[i]);
}
fclose(out);
}
int max(int x, int y)
{
int mm = 0, mi;
for(int i = 0; i <= x; i ++) {
int j = x – i;
if(mm < in_data[j][y] + in_data[i][y - 1]) {
mm = in_data[j][y] + in_data[i][y – 1];
mi = i;
}
}
k = mi;
return mm;
}
void follow()
{
int i = n;
int cnt = 0;
for(int j = m; j >= 1; j --) {
fol[++ cnt] = i – table2[i][j];
i = table2[i][j];
}
}
10. 백화점 쿠폰 받기
[문제] 한 소비자가 4만원을 갖고 두 개의 백화점에서 각각 만원단위로 물건을 샀을 경우 얻을 수 있는 쿠폰은 다음과 같다.
input.txt
4 2
1 5 1
2 6 5
3 7 9
4 10 15
output.txt
0 4
15
[점화식]
1) i 백화점에서 0원의 물건을 사는 경우
c[i][j] = c[i-1][j] + a[i][0]
2) i백화점에서 1만원의 물건을 사는 경우
c[i][j] = c[i-1][j-1]+a[i][1]
3) i백화점에서 j만원의 물건을 사는 경우
c[i][j] = c[i-1][0] + a[i][j]
결론적으로 c[i][j] = MAX{ c[i-1][j-k] + a[i][k]}
(단, k는 0<=k<=j 인 정수)