Dynamic Programming (동적 계획법)

1. Dynamic Programming이란?

: 복잡한 문제를 "작은 문제"로 나누어 푸는 방법

- "작은 문제"에서 최적의 결과 → 전체의 최적의 결과

- 앞에서 구한 결과를 다음 계산 때 이용하는 방향 (재사용)

 

2. 방식

1) 하향식 알고리즘(Top-Down)

: 큰 문제에서 재귀함수를 호출하여 푸는 방식 → "작은 문제"가 중복되어 풀림

ex> 막대 자르기 문제 : 어떻게 잘라야 최대 이익으로 팔 수 있는가(길이에 따라 가격 책정이 다름)

Function cutRod(p, n){
    if(n = 0) return 0;
    q <- p[n];
    for i = 1 to n-1 {
        q <- max{q, p[i] +  cutRod(p, n-i)};
    }
    return q;
}

- 한계 : 내부에 시스템 호출 stack을 사용하는 overhead 발생 가능

   → 상향식 : 계산한 결과를 memory에 저장하여 재사용

 

 

2) 상향식 알고리즘(Bottom-Up)

: 작은 문제부터 풀기 시작 → 큰 문제를 풀 때 참조하는 작은 문제들의 결과가 이미 구해진 상태

ex> 막대 자르기 문제

Function bottomUpCutRod(p, n){
    r[0] <- 0;
    for j = 1 to n{
        q <- -inf;
        for i = 1 to j {
            q <- max{q, p[i] + r[j-i]};
        }
        r[j] <- q;
    }  
    return q;
}

 

3. 알고리즘 구상 방향

- 작은 문제들의 최적값이 전체의 최적값과 연관성이 있는지 확인

- 재귀적인 성질(재귀 함수, 앞에서 계산한 값을 재사용) 활용

- Memoization_메모리에 저장 : 중복 계산은 최대한 피하는 방향

 

4. 예시

(1) 피보나치 수를 구하는 함수

- 과정

1. 문제를 부분 문제로 분할
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
Fibonacci(n-1) = Fibonacci(n-2) + Fibonacci(n-3)
...
Fibonacci(2) = Fibonacci(1) + Fibonacci(0)

2. 가장 작은 부분 문제부터 해 구하기

3. 결과를 테이블에 저장하고, 저장된 부분 문제의 해를 이용해 상위 문제의 해 구하기(Memoization)

- 상향식 알고리즘

public int fibonacci(int n){
    int[] f = new int[n+1];
    f[0] = 0; f[1] = 1;
    for(int i = 2; i <= n ; i++){
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}