C언어 막대 자르기(Rod cutting in C) - 동적 프로그래밍(Dynamic-Programming)

C언어 막대 자르기(Rod cutting in C) - 동적 프로그래밍(Dynamic-Programming)

- 어떤 막대(rod)를 그들의 최종 값을 최대화하는 방식으로 작은 길이의 막대로 자르는 것

- 막대의 어느 부분을 자를 것인지 선택하는 간단한 문제

- 막대의 길이 n(inches)와 가격 p를 고려하여 자른 부위를 팔았을 때 얻을 수 있는 최고의 수익 r을

결정하는 것

- 만약 자른 길이의 가격이 충분히 크다면, 최적의 솔루션은 자르는 것을 전혀 요구하지 않는다.

- 막대의 길이가 n이면 총 2ⁿ-¹의 다른 방식으로 자를 수 있다.

( 자르지 않는 경우의 수도 포함 )

the strategy of the rod-cutting, cite : introduction to algoritms 3/E

1. 단순 재귀로 구현하기(Recursive top-down implementation)

주어지는 표는 다음과 같다.

length i	1	2	3	4	5	6	7	8	9	10
price Pi	1	5	8	9	10	17	17	20	24	30

만약 단순 재귀로 최적의 해를 구해보자. 그렇다면 소스는 아래와 같다.

max는 단순히, 두 수익 중 큰 수익을 반환하는 함수이다.

 

/* int max( int , int) This function returns the larger value between two. */ int max( int p_r, int n_r) {     if( p_r > n_r)         return p_r;     return n_r; }

/* int cut_rod( int *, int) this function calls it self recusively to compute the revenue. */ int cut_rod( int *p, int n) {     int i, q;     int r;     // initialize the revenue     q   = REVENUE;     if( n == 0) // the length of a rod is 0         return 0;     for( i = 1 ; i <= n ; i ++)     {         // if the length of a rod is over the maximum revenue.         if( i >= PMAX)         {             r   = PMAX-1;         }         else         {             r   = i-1;         }         // call itself recursively to solve subproblems         q   = max( q, p[r] + cut_rod( p, n - i));     }     return q; }

 

 

만약, 위의 코드로 프로그램을 작성하여 실행시킨다면, n의 값이 1 증가할 때마다 수행 시간은 약

두 배가 된다.

왜 위의 코드가 비효율적일까?

위의 코드는 같은 파마리터 값으로 자기 자신을 재귀적으로 지나치게 호출한다.

따라서, 같은 하위 문제를 반복적으로 수행하고 있는 것이기 때문이다.

2. 최적의 막대 자르기를 위해 동적 프로그래밍 사용하기

(Using dynamic programming for optimal rod cutting)

동적 프로그래밍 메소드는 다음과 같이 동작한다.

(1) 하위 문제들이 오로지 한 번만 해결되도록 하위 문제들을 정렬하고 이것의 해결책을 저장한다.

( 만약 나중에 해당 하위 문제를 참고하고 싶으면, 재계산을 하지 않아도 된다. )

(2) 동적 프로그래밍은 (1)을 위해 추가적인 메모리를 사용한다. (time-memory trade-off)

( 지수 시간으로 표현된 수행 시간이, 다항 시간으로 변형될 것이다. )

3. 동적 프로그램의 접근 방식(a dynamic-programming approach)

(1) top-down with memoization

재귀적으로 이전에 계산된 결과를 저장하는 방식

- 각 하위 문제들의 결과를 저장하기 위한 수정된 일반적인 방식으로 처리를 기록한다.

- 처음에는 현재 하위 문제가 이전에 처리된 것인지 확인한다.

=> 처리된 하위 문제라면 저장된 값을 반환하고, 현재 레벨에서 추가적으로 계산된 값을 저장한다.

=> 처리되지 않은 하위 문제라면 일반적인 방식으로 값을 계산하여 저장한다.

(2) bottom-up method

일반적으로 하위 문제 크기의 관점에 의존적이다.

- 하위 문제들을 크기로 오름차순 정렬하고, 그것들을 계산한다.

- 부분적인 하위문제를 해결할 때, 이미 해당 하위 문제에 관련된 작은 문제들이 해결된 상태면 그것들의 해결책을 통해 현재 레벨의 해결책을 계산하여 저장한다.

- 각 하위 문제를 단 한번만 해결한다.

- 처음 접하는 문제를 봤을 때, 이미 그 문제의 모든 전제조건을 모두 해결한 상태이다.

일반적으로 두 알고리즘은 비슷한 수행시간을 산출하지만, the bottom-up method가 프로시저 호출에 대해 더 낮은 오버헤드를 가지기 때문에 주로 더 나은 고정적인 결과를 가진다.

4. 동적 프로그램을 이용한 막대 자르기(rod-cutting using dynamic-programming)

(1) top-down with memoization

/* int memoized_cut_rod( int *, int, int *) using dynamic-programming, improve the running time of the cut_rod. */ int memoized_cut_rod( int *p, int n, int *ar) {     int q, i, r;     // examine whether this problem is solved.     if( ar[n] >= 0)     {         return ar[n];     }     if( n == 0)     {         q   = 0;     }     else     {         q   = REVENUE;         for( i = 1 ; i <= n ; i ++)         {             // if the length of a rod is over the maximum revenue.             if( i >= PMAX)             {                 r   = PMAX - 1;             }             else             {                 r   = i - 1;             }             // call itself recursively to solve subproblems             q   = max( q, p[r] + memoized_cut_rod( p, n - i, ar));         }     }     ar[n]   = q; // save the result at this level.     return q; }

(2) bottom-up method

/* int bottom_up_cut_rod( int *, int) it arranges the subproblems by the size. */ int bottom_up_cut_rod( int *p, int n) {     int ar[NMAX] = {0,};     int i, j, q, r;     for( i = 1 ; i <= n ; i ++)     {         q   = REVENUE;         for( j = 1 ; j <= i ; j ++)         {               // if the length of a rod is over the maximum revenue.             if( j >= PMAX)             {                 r   = PMAX - 1;             }             else             {                 r   = j - 1;             }             // find the optimal revenue from the subproblems.             q   = max( q, p[r] + ar[i - j]);         }         ar[i]   = q;     }     return ar[n]; }

 

5. 수행 시간 비교

(1) 일반(original) vs 메모이즈드(memoized) vs 바텀-업(bottom-up)

- 막대 길이 30을 기준으로한 결과는 다음과 같다.

 

(2) 메모이즈드(memoized) vs 바텀-업(bottom-up)

- 막대 길이 500을 기준으로 한 결과는 다음과 같다.

 

※오리지널의 경우, 작성자의 컴퓨터 기준에서 (n/2) * 2^(n-29)초의 수행시간이 걸린다.

즉, 막대길이 500의 경우, 250 * 2^471 초로 어마어마한 시간이지만, 동적 프로그래밍을

이용하면 고작 0.005초 미만의 시간이 걸린다.