반응형
12-24 00:25
- Today
- Total
Link
개발하는 고라니
[알고리즘] 동적 프로그래밍 (DP, Dynamic Programming) 본문
반응형
# 학습목표
- 동적 프로그래밍이 무엇인지 이해한다.
- 어떤 특성을 가진 문제가 동적 프로그래밍의 적용 대상인지 감지할 수 있도록 한다.
- 기본적인 몇 가지 문제를 동적 프로그래밍으로 해결할 수 있도록 한다.
# 배경
- 재귀적 해법
- 큰 문제에 닮음꼴의 작은 문제가 깃든다.
- 잘 쓰면 보약, 잘못 쓰면 맹독
- 관계중심으로 파악함으로써 문제를 간명하게 볼 수 있다.
- 재귀적 해법을 사용하면 심한 중복 호출이 일어나는 경우가 있다.
- 재귀적 해법의 양면성
- 바람직한 예
- 퀵정렬, 병합정렬 등의 정렬 알고리즘
- 계승(Factorial) 구하기
- 그래프의 DFS(Depth First Search) 등
- 치명적인 예
- 피보나치수 구하기
- 행렬곱셈 최적순서 구하기
- 바람직한 예
# 도입 문제 : 피보나치수 구하기
* f(n) = f(n-1) + f(n-2)
f(1) = f(2) = 1
* 아주 간단한 문제이나, 동적 프로그래밍의 동기와 구현이 다 포함 되어있다.
fib(n)
{
if(n = 1 or n = 2)
then return 1;
else return (fib(n-1) + fib(n-2));
}
//엄청난 중복 호출이 존재한다.
* 피보나치수를 구하는 동적 프로그래밍 알고리즘
- 이미 일어나진 일들을 다음 계산을 위해 더 작은 문제의 해를 메모해두는 방식 (ex, 배열 또는 표 등)
fibonacci(n)
{
f[1] <- f[2] <- 1;
for i <- 3 to n
f[i] <- f[i-1] + f[i-2];
return f[n];
}
//선형시간에 끝난다.
- Memoization(메모하기)
- 상향식 / 하향식
- int f[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, ... }
# 동적 프로그래밍의 적용 요건
- 최적 부분구조 (optimal substructure)
- 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함됨
- 재귀호출시 중복 (overlapping recursive calls)
- 재귀적 해법으로 풀면 같은 문제에 대한 재귀호출이 심하게 중복됨
# 문제 예 1: 행렬 경로 문제
- 양수 원소들로 구성된 n X n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동
- 이동 방법 (제약 조건)
- 오른쪽이나 아래쪽으로만 이동할 수 있다.
- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.
- 목표 : 행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 잇는 수들을 더한 값이 최소(최대)화되도록 한다.
6 | 7 | 12 | 5 |
5 | 3 | 11 | 18 |
7 | 17 | 3 | 3 |
8 | 10 | 14 | 9 |
재귀 알고리즘
matrixPath(i, j)
->(i, j)에 이르는 최고점수
{
if(i = 0 or j = 0) then return 0;
else return (m(ij) + max(matrixPath(i - 1, j), matrixPath(i, j - 1)));
}
DP 알고리즘
matrixPath(n)
->(n, n)에 이르는 최고점수
{
for i <- 0 to n
c[i, 0] <- 0;
for j <- 1 to n
c[0, j] <- 0;
for i <- 1 to n
for j <- 1 to n
c[i, j] <- m(ij) + max(c[i-1, j], c[i, j-1]);
return c[n, n];
}
0 | 0 | 0 | 0 | 0 |
0 | 6 | 7 | 12 | 5 |
0 | 5 | 3 | 11 | 18 |
0 | 7 | 17 | 3 | 3 |
0 | 8 | 10 | 14 | 9 |
0 | 0 | 0 | 0 | 0 |
0 | 6 | 13 | 25 | 30 |
0 | 11 | 16 | 36 | 54 |
0 | 16 | 19 | 39 | 57 |
0 | 24 | 34 | 53 | 66 |
# 문제 예 2: 돌 놓기
- 3 X N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 잇다.
- 조약돌을 놓는 방법 (제약조건)
- 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다.
- 각 열에는 적어도 하나 이상의 조약돌을 놓는다.
- 목표 : 돌이 놓인 자리에 잇는 수의 합을 최대가 되도록 조약돌 놓기
6 | 7 | 12 | -5 | 5 | 3 | 11 | 3 |
-8 | 10 | 14 | 9 | 7 | 13 | 8 | 5 |
11 | 12 | 7 | 4 | 8 | -2 | 9 | 4 |
* 예) 11에 놓음 -> 10에 놓음 ->
12 or 7에 놓음(둘 다 놓아도 됨) -> 9에 놓음 ->
5 or 8에 놓음(둘 다 놓아도 됨) -> 13에 놓음 ->
11 or 9에 놓음(둘 다 놓아도 됨) -> 5에 놓음
* i열과 i-1열의 관계
i-1 | i | ||||||
6 | 7 | 12 | -5 | 5 | 3 | 11 | 3 |
-8 | 10 | 14 | 9 | 7 | 13 | 8 | 5 |
11 | 12 | 7 | 4 | 8 | -2 | 9 | 4 |
- i열의 1번째 원소인 7의 관점에서 (패턴 2)
i-1 | i | ||||||
6 | 7 | 12 | -5 | 5 | 3 | 11 | 3 |
-8 | 10 | 14 | 9 | 7 | 13 | 8 | 5 |
11 | 12 | 7 | 4 | 8 | -2 | 9 | 4 |
i-1 | i | ||||||
6 | 7 | 12 | -5 | 5 | 3 | 11 | 3 |
-8 | 10 | 14 | 9 | 7 | 13 | 8 | 5 |
11 | 12 | 7 | 4 | 8 | -2 | 9 | 4 |
i-1 | i | ||||||
6 | 7 | 12 | -5 | 5 | 3 | 11 | 3 |
-8 | 10 | 14 | 9 | 7 | 13 | 8 | 5 |
11 | 12 | 7 | 4 | 8 | -2 | 9 | 4 |
- i - 1 열이
- 패턴 1로 끝나거나
- 패턴 3으로 끝나거나
- 패턴 4로 끝나거나
- 중에서 최대값을 갖을 수 있는 경우로 선택한다.
재귀 알고리즘
pebble(i, p)
{
-> i열이 패턴 p로 놓일 때의 i열 까지의 최대 점수 합 구하기
-> w[i, p] : i열이 패턴 p로 놓일 때 i열에 돌이 놓인 곳의 점수 합
p는 {1, 2, 3, 4}를 포함
if(i = 1)
then return w[1, p];
else {
max <- -무한대;
for q <- 1 to 4 {
if(패턴 q가 패턴 p와 양립)
then{
tmp <- pebble(i-1, q);
if(tmp > max) then max <- tmp;
}
}
return (max + w[i, p]);
}
}
DP 방식
pebbleSum(n)
-> n열 까지 조약돌을 놓은 방법 중 최대 점수 합 구하기
{
return max{pebble(n, p)}; //p = 1, 2, 3, 4
}
/* pebble(i, 1), ..., pebble(i, 4) 중 최대값이 최종 답 */
# DP 적용
- DP 요건 만족
- 최적 부분구조
- pebble(i, x)에 pebble(i-1, x)이 포함됨
- 즉, 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함됨
- 재귀 호출시 중복
- 재귀적 알고리즘에 중복 호출 심함 (비효율)
- 최적 부분구조
DP 알고리즘
pebble(n)
{
for p <- 1 to 4
peb[1, p] <- w[1, p];
for i <- 2 to n
for p <- 1 to 4
peb[i, p] <- max {peb[i-1, q]} + w[i, p]; //p와 양립하는 패턴 q
return max {peb[n, p]};
}
/* 복잡도 : 빅세타(n) */
* 패턴
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
패턴 1 | 6 | 18(11+7) | 39(27+12) | 29(34-5) | 59(54+5) | 65(62+3) | 91(80+11) | 92(89+3) |
패턴 2 | -8 | 27(17+10) | 32(18+14) | 54(46+9) | 50(43+7) | 80(67+13) | 73(65+8) | 105(100+5) |
패턴 3 | 11 | 18(12+6) | 34(27+7) | 43(39+4) | 62(54+8) | 57(59-2) | 89(80+9) | 95(91+4) |
패턴 4 | 17 | 11(19-8) | 46(27+19) | 31(32-1) | 67(54+13) | 51(50+1) | 100(80+20) | 80(73+7) |
6 | 7 | 12 | -5 | 5 | 3 | 11 | 3 |
-8 | 10 | 14 | 9 | 7 | 13 | 8 | 5 |
11 | 12 | 7 | 4 | 8 | -2 | 9 | 4 |
# 문제 예 3: 행렬 곱셈 순서
- 행렬 A, B, C
- (AB)C = A(BC)
- 예 : A:10 X 100, B:100 X 5, C:5 X 50
- (AB)C : 7500번의 곱셈 필요
- A(BC) : 75000번의 곱셈 필요
- A1, A2, A3, ..., An을 곱하는 최적의 순서는?
- 총 n-1회의 행렬 곱셈을 어떤 순서로 할 것인가?
# 과제 결과
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 50
#define TABLE_SIZE 5
//1. 교재 290쪽 연습문제 06을 동적프로그래밍 방법으로 완성하시오.
int maximum(int x, int y, int z)
{
if (x > y)
if (x > z)
return x;
else
return z;
else
if (y > z)
return y;
else
return z;
}
int table[TABLE_SIZE][TABLE_SIZE] = {
{0, 0, 0, 0, 0},
{0, 6, 7, 12, 5},
{0, 5, 3, 11, 18},
{0, 7, 17, 3, 3},
{0, 8, 10, 14, 9} };
int DP_table[TABLE_SIZE][TABLE_SIZE];
void init_table(int a[][TABLE_SIZE]) {
for (int i = 0; i < TABLE_SIZE; i++)
for (int j = 0; j < TABLE_SIZE; j++)
a[i][j] = 0;
}
void print_table(int a[][TABLE_SIZE]) {
printf("# 행렬: \n");
for (int i = 0; i < TABLE_SIZE; i++) {
for (int j = 0; j < TABLE_SIZE; j++)
printf("%2d, ", a[i][j]);
printf("\n");
}
}
int maxPath(int n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
DP_table[i][j] = maximum( (DP_table[i-1][j-1] + table[i][j]), (DP_table[i - 1][j] + table[i][j]), (DP_table[i][j - 1] + table[i][j]) ); //좌측 대각선, 위, 좌측으로부터
}
}
return DP_table[n][n];
}
/*
2. N개 계단을 올라가려고 한다. 매번 계단을 1칸 또는 2칸을 올라갈 수 있다.
맨 위까지 올라갈 수 있는 방법의 수는 몇 개인지 구하는 프로그램을 동적 프로그래밍 방법으로
완성하시오.
*/
int stairs[MAX_SIZE];
int upstair(int n) {
stairs[0] = 0;
stairs[1] = 1;
stairs[2] = 2;
for (int i = 3; i <= n; i++) {
stairs[i] = stairs[i - 1] + stairs[i - 2];
printf("%d 계단을 오르는 경우의 수 : [%d]\n", i, stairs[i]);
}
return stairs[n];
}
/*
3. 어느 우체국에는 80원짜리, 50원짜리, 10원짜리 우표가 있다.
(1) 특정 금액의 우편요금을 위해 사용하는 최소 개수의 우표 개수를 동적프로그래밍으로 구하시오. (10, 20, 30, 40, 50 … 300원을 만드는 최소 우표 개수를 구하는 표를 완성하시오).
선택사항으로, 최적의 해가 각 우표를 몇 장씩 사용하는는지도 출력하시오.
(2) 만약, 우체국 직원이 그리디 알고리즘을 적용한다면 어떤 조합으로 우표들을 받게 되는지
계산하는 프로그램을 작성하고, 그 결과가 최적)의 결과인지 (1)과 비교하시오.
*/
#define STAMP_SIZE 41
int stamp[5][STAMP_SIZE]; //300원은 index 30
int greedy[5][STAMP_SIZE];
void init_stamp(int a[][STAMP_SIZE]) {
for (int i = 0; i < STAMP_SIZE; i++)
a[0][i] = 10 * i;
for (int i = 0; i < 5; i++)
a[i][0] = 0;
for (int i = 1; i < STAMP_SIZE; i++)
a[4][i] = 9999;
}
//0: 0 10 20 30 40 50 60 ... 300
//1: 80원 짜리
//2: 50원 짜리
//3: 10원 짜리
//4: 우표 개수
int d[4] = {0, 80, 50, 10 };
int minStamp(int n) {
int index = n / 10; //금액의 인덱스
for (int i = 1; i <= index; i++) {
for (int j = 1; j <= 3; j++) {
/*
# d[j]:우표 액면가
# stamp[0][i]:현재 금액
# stamp[4][i-(d[j]/10]+1:현재금액에서 d[j]를 뺀 금액의 우표 수
# stamp[4][i]:현재 금액의 우표 수
*/
if (d[j] <= stamp[0][i] && stamp[4][i - (d[j] / 10)] + 1 < stamp[4][i]) {
stamp[4][i] = stamp[4][i - (d[j] / 10)] + 1; //최적해
stamp[3][i] = stamp[3][i - (d[j] / 10)]; //10원짜리
stamp[2][i] = stamp[2][i - (d[j] / 10)]; //50원짜리
stamp[1][i] = stamp[1][i - (d[j] / 10)]; //80원짜리
stamp[j][i]++; //j번째 우표 액면가 증가
printf("-------------------------\n");
printf("# %d원의 최적해 : %d장\n80원 : %d개\n50원 : %d개\n10원 : %d개\n", stamp[0][i], stamp[4][i], stamp[1][i], stamp[2][i], stamp[3][i]);
}
}
}
return stamp[4][index];
}
int greedyStamp(int n) {
int index = n / 10, value; //금액의 인덱스
for (int i = 1; i <= index; i++) {
value = greedy[0][i];
for (int j = 1; j <= 3; j++) {
if (value / d[j] > 0) {
greedy[j][i] = value / d[j];
value = value % d[j];
}
}
greedy[4][i] = greedy[1][i] + greedy[2][i] + greedy[3][i];
}
printf("-------------------------\n");
printf("# %d원의 Greedy : %d장\n80원 : %d개\n50원 : %d개\n10원 : %d개\n", greedy[0][index], greedy[4][index], greedy[1][index], greedy[2][index], greedy[3][index]);
return greedy[4][index];
}
int main(void) {
int select = 0, n, val = 0;
while (select != -1) {
printf("====================================================\n");
printf("(1) 행렬의 최적해 \n(2) 계단 올라가기 \n(3) 우표 문제 \n(4) \n(-1) Exit\n");
printf("====================================================\n");
scanf("%d", &select);
switch (select) {
case 1:
init_table(DP_table);
print_table(table);
printf("최적해를 얻고자 하는 (n,n) 경로의 n을 입력하세요. (단, 0 < n < 5)\n");
scanf("%d", &n);
printf("# (%d, %d)의 최적해는 %d 입니다.\n", n, n, maxPath(n));
print_table(DP_table);
break;
case 2:
printf("몇 개의 계단을 올라갈까요?\n");
scanf("%d", &n);
printf("# %d개의 계단을 올라갈 때 경우의 수는 %d개 입니다.\n", n, upstair(n));
break;
case 3:
init_stamp(stamp);
init_stamp(greedy);
//print_stamp(stamp);
printf("특정 금액을 입력하세요. (단, n <= 400)\n");
scanf("%d", &n);
val = minStamp(n);
val = greedyStamp(n);
break;
case 4:
break;
}
}
return 0;
}
반응형
'Programming > 알고리즘' 카테고리의 다른 글
[알고리즘] 크루스칼(Kruskal) 알고리즘 (0) | 2021.01.28 |
---|---|
[알고리즘] 선택 / 버블 / 삽입 정렬 (0) | 2021.01.26 |
[알고리즘] 너비 우선 탐색(Breadth-First Search, BFS) (0) | 2021.01.20 |
[알고리즘] 깊이 우선 탐색(Depth-First Search, DFS) (0) | 2021.01.20 |
[알고리즘] Greedy 알고리즘 (0) | 2020.12.06 |
Comments