반응형
05-17 07:25
Today
Total
Link
«   2024/05   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
Recent Posts
Recent Comments
Tags more
관리 메뉴

개발하는 고라니

[알고리즘] 동적 프로그래밍 (DP, Dynamic Programming) 본문

Programming/알고리즘

[알고리즘] 동적 프로그래밍 (DP, Dynamic Programming)

조용한고라니 2020. 12. 7. 01:23
반응형

# 학습목표

  • 동적 프로그래밍이 무엇인지 이해한다.
  • 어떤 특성을 가진 문제가 동적 프로그래밍의 적용 대상인지 감지할 수 있도록 한다.
  • 기본적인 몇 가지 문제를 동적 프로그래밍으로 해결할 수 있도록 한다.

 

# 배경

  • 재귀적 해법
    • 큰 문제에 닮음꼴의 작은 문제가 깃든다.
    • 잘 쓰면 보약, 잘못 쓰면 맹독
      • 관계중심으로 파악함으로써 문제를 간명하게 볼 수 있다.
      • 재귀적 해법을 사용하면 심한 중복 호출이 일어나는 경우가 있다.
  • 재귀적 해법의 양면성
    • 바람직한 예
      • 퀵정렬, 병합정렬 등의 정렬 알고리즘
      • 계승(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
'Programming/알고리즘' Related Articles more
Comments