다이나믹 프로그래밍 (Dynamic Programming)

참고

https://ko.wikipedia.org/wiki/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 위키백과, 우리 모두의 백과사전

정의

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

• 두 가지 방법으로 문제를 해결할 수 있다.

  • Top-down
  • Bottom-up
• 다이나믹 프로그래밍에서는 구하는 답이 반복이 되므로, 구한 값을 배열에 저장해둔다. (메모이제이션)

Top-down

• 재귀함수 호출로 문제를 풀 수 있다.

int memo[100];
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        if (memo[n] > 0) {
            return memo[n];
        }
    
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        
        return memo[n];
    }
}

Bottom-up

• 작은 문제부터 순서대로 해결한다.

• 작은 문제를 해결하면서 순서대로 해결하다 보면, 큰 문제도 해결할 수 있다.

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