Dynamic Programming(동적계획법)

Basic Concept

---

The divide and conquer algorithm works in problems such as Mergesort, where the smaller instances are unrelated. However, in problems such as nth Fibonacci term, the smaller instances are related. In problems where the smaller instances are related, a divide-and conquer algorithm often ends up repeatedly solving common instances, and the result is a very inefficient algorithm. Recall that the number of terms computed by the divide-and-conquer algorithm for determining the nth Fibonacci term is exponential in n. To compute the fifth Fibonacci term we need to compute the fourth and third Fibonacci terms. However, the determinations of the fourth and third Fibonacci terms are related in that they both require the second Fibonacci term. Because the divide-and-conquer algorithm makes these two determinations independently, it ends up computing the second Fibonacci term more than once.

 

nth Fibonacci Term using Divide-and-Conquer

분할정복법을 사용하여 피보나치 수열을 풀면 fib(3)과 fib(4)에서 fib(2)를 중복 계산하기 때문에 비효율적인 알고리즘이 된다.

// nth Fibonacci Term using Divide-and-Conquer
int fib(int n)
{
    if (n <= 1)
        return n;
    else
        return fib(n-1) + fib(n-2);
}

// 5th Fibonacci Term : fib(2)를 두 번 이상 계산하는 비효율 발생
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2) // fib(4)에서도 fib(2)를 독립적으로 계산
fib(3) = fib(2) + fib(1) // fib(3)에서도 fib(2)를 독립적으로 계산
...

 

nth Fibonacci Term using Dynamic Programming

피보나치 수열 문제는 동적계획법을 사용하면 훨씬 더 효율적인 계산이 가능해진다. n번째 항의 값을 계산할 때 이미 구해놓은 n-1번째 항과 n-2번째 항을 이용하기 때문이다.

// nth Fibonacci Term using Dynamic Programming
int fibonacci(int n)
{
    int i;
    int f[n];
    f[0] = 0;

    if (n > 0)
    {
        f[1] = 1;
        for (i = 2; i <= n; ++i)
            f[i] = f[i-1] + f[i-2];
    }

    return f[n];
}

 

👉 분할정복법으로 피보나치 수열을 계산하면 같은 항을 여러번 계산하는 결과를 초래하므로 비효율적인 알고리즘이 된다. 분할정복법은 합병정렬과 같이 분할된 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합한 방식이다.

 

 

The Dynamic Programming Approach

---

Dynamic programming takes the opposite approach of divide-and-conquer. Dynamic programming is similar to divide-and-conquer in that an instance of a problem is divided into smaller instances. However, in this approach we solve small instances first, store the results, and later, whenever we need a result, look it up instead of recomputing it. The terms dynamic programming comes from control theory, and in this sense programming means the use of an array (table) in which a solution is constructed.

 

Bottom-up approach

1. Establish a recursive property that gives the solution to an instance of the problem.
2. Solve an instance of the problem in a bottom-up fashion by solving smaller instances first.

 

👉 동적계획법은 원래의 문제를 더 작은 문제로 분할한다는 점에서 분할정복법과 유사하다. 이 기법은 먼저 작은 문제들을 풀어 그 결과를 저장하고 나중에 필요할 때마다 값을 재계산하지 않고 찾아보며 최종 해에 도달하게 되는 bottom-up 방식이다. 분할정복법의 top-down 방식과는 정반대의 개념이다.

“동적계획법(동적프로그래밍)”이라는 용어는 제어 이론에서 나온다. 여기서 “프로그래밍”은 솔루션이 구성되는 배열(테이블)의 사용을 의미한다.