[알고리즘 C언어] 6.동적 프로그래밍

커다란 문제를 해결하는 과정을 여러 단계로 나누어 해결하는 알고리즘들이 있어요.

그 중에 동적 프로그래밍은 현재 단계에서 다음 단계로 진행하면서 알 수 있는 정보를 학습해요.

그리고 이 학습 정보를 이용하여 다음 단계로 진행하여 전체 문제를 해결하는 알고리즘이예요.

이전 단계에서 다음 단계로 진행할 수 있는 경우의 수가 고정일 때는 간단하게 문제를 해결할 수 있어요.

하지만 이전 단계에서 다음 단계로 진행할 수 있는 경우의 수가 많을 때는 스택을 이용해서 문제를 해결하여 비교적 간단하게 만들 수 있어요. 하지만 수행 성능은 떨어질 수 있어요.

먼저 이전 단계에서 다음 단계로 진행할 수 있는 경우의 수가 고정인 문제로 대표적인 것이 피보나치 수열을 구 문제예요.

여기에서는 동적 프로그래밍으로 작성한 것과 그렇지 않은 것을 비교해 보기로 할게요.

다음은 동적 프로그래밍 기법을 사용하지 않은 피보나치 수열의 n 항을 구하는 함수예요.

unsigned long long Fibonacci(unsigned int n)
{
    long long result = 1;
    if(n<=0)
    {
        return 0;
    }
    if((n==1)||(n==2))
    {
        return 1;
    }
    else
    {
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

다음은 동적 프로그래밍 기법을 사용한 함수예요.

unsigned long long value_table[100]={0,1,1};
unsigned long long Dynamic_Fibonacci(unsigned int n)
{
    long long result = 1;
    if(n<=0)
    {
        return 0;
    }
    if(value_table[n])
    {
        return value_table[n];
    }
    else
    {
        unsigned long long fval=0,sval=0;
        fval = Dynamic_Fibonacci(n-1);

        sval = Dynamic_Fibonacci(n-2);
        
        value_table[n] = fval + sval;
        return fval + sval;
    }
}

동적 프로그래밍 기법에서는 경험을 통해 얻은 휴리스틱(Heuristic) 정보를 기억하는 value_table이 있어요.

그리고 특정 항을 계산한 적이 없다면 계산하여 value_table에 기억하게 해요.

만약 이미 계산한 적이 있다면 value_table에 기억했던 값을 반환하는 거예요.

#include <stdio.h>
#include <time.h>
unsigned long long Fibonacci(unsigned int n)
{
    long long result = 1;
    if(n<=0)
    {
        return 0;
    }
    if((n==1)||(n==2))
    {
        return 1;
    }
    else
    {
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}


unsigned long long value_table[100]={0,1,1};
unsigned long long Dynamic_Fibonacci(unsigned int n)
{
    long long result = 1;
    if(n<=0)
    {
        return 0;
    }
    if(value_table[n])
    {
        return value_table[n];
    }
    else
    {
        unsigned long long fval=0,sval=0;
        fval = Dynamic_Fibonacci(n-1);

        sval = Dynamic_Fibonacci(n-2);
        
        value_table[n] = fval + sval;
        return fval + sval;
    }
}


int main(void)
{
    int i = 0;
    long long value=0,value2=0;
    clock_t st,et;

    for( i = 20; i<35;i++)
    {
        printf("%d Test\n",i);
        st = clock();
        value = Fibonacci(i);
        et = clock();
        printf("Fibonacci(%d)=%lld , %d clocks\n",i, value, et-st);
        
        st = clock();
        value2 = Dynamic_Fibonacci(i);
        et = clock();
        printf("Fibonacci(%d)=%lld, %d clocks\n",i,value2,et-st);
        
    }
    
    return 0;
}

다음은 이 두 개의 알고리즘으로 실행했을 때의 실행 화면입니다.

피보나치 수열 수행 시간 분석 예제 실행 결과
피보나치 수열 수행 시간 분석 예제 실행 결과

n이 작을 때는 차이가 없지만 n이 커지면 그 차이는 상상 이상으로 커집니다.

이 때 각 단계의 상태를 경험(Heuristic) 정보라 부르며 이를 설계하는 것이 중요합니다. 그리고 현재 단계에서 진행할 수 있는 여러 단계들을 자료구조에 보관하여 필요할 때 하나 하나 꺼내어 수행해야 하는데 이 때 사용하는 자료구조가 스택입니다.

다음은 동적 알고리즘의 의사 코드입니다.

동적 알고리즘

초기 경험 정보를 생성

스택에 초기 경험 정보 Push

반복(스택이 빌 때까지)

스택에서 경험 정보를 Pop

꺼낸 온 경험에서 발생할 수 있는 다음 경험 정보 조사

반복(다음 경험 정보들을 순차적으로)

조건(결과에 도달하지 않았다면)

스택에 경험 정보를 Push

그렇지 않다면

결과에 보관

여기에서는 바구니에서 공을 꺼내는 순열 문제와 그래프 상에서 경로를 찾는 방법 중에 동적 알고리즘을 사용하는 깊이 우선 탐색(DFS, Depth First Search)을 살펴볼게요.

C언어 알고리즘