[Algorithm] 동적 계획법 (Dynamic Programming)

날짜:

동적 계획법(Dynamic programming) : 어떤 결과값을 도출하기 위해 이미 결과를 찾아 저장해놨던 이전의 특정 값을 재활용하는 방법. 쉽게 말해 이전 값을 재활용해서 결과를 찾아나가는 방식이다.
가장 기본적이고 유명한 예시 중에 피보나치 수열이 있다. 피보나치 수열을 구현하는 방법에는 재귀 함수를 이용한 방법과 동적 프로그래밍을 이용한 방법이 있다.




1. 재귀 함수를 이용한 피보나치 수열


가장 대표적으로 잘 알려진 방법이다. Recursive_Fibo 함수를 재귀적으로 호출해서 만들어준다.

ull Recursive_Fibo(int n){
    
    if(n == 1 || n == 2) return 1;
    return Recursive_Fibo(n - 1) + Recursive_Fibo(n - 2);
}

재귀 함수는 일단 보기 편하고 다른 변수를 많이 사용하지 않아도 표현할 수 있다는 장점이 있다. 좀 있다 설명할건데, 아래에서 설명할 다이나믹 프로그래밍에서는 vector를 이용해 결과값을 저장하기 때문에 다른 변수를 써야하지만 재귀 함수는 자신을 return 해주기 때문에 변수 자체를 많이 쓰지 않는다.

문제는 재귀 함수를 사용할 경우 반복문에 비해서 메모리를 많이 먹고 느리다. 
보통 함수를 호출할 때 스택에 여러 변수들과 return 값, 함수가 종료되고 돌아갈 주소 등이 저장된다. 이 때 재귀 함수를 쓸 경우 반복적으로 호출하기 때문에 스택에 메모리가 많이 쌓이고, 상황에 따라 stack overflow가 발생할 수 있다. 또한 스택 프레임을 구성, 해제하는 과정에서 당연히 시간이 들기 때문에 기본적인 반복문에 비해 시간도 많이 걸린다.
이런 단점을 보완하고자하는 방법이 반복문을 이용한 동적 계획법(dynamic programming) 이다. 반복문을 사용하며 vector나 배열을 이용해 결과값을 저장하고 그것을 다시 재활용하기 때문에 재귀함수에서 O(n^2) 시간이 들 수 있는 알고리즘을 O(n) 시간으로 단축할 수 있는 효과가 있다.



2. 동적 계획법을 이용한 피보나치 수열



ull DP_Fibo(int n){

    Fibo.push_back(0);
    Fibo.push_back(1);
    Fibo.push_back(1);
    
    for(int i = 3; i <= n; i++){
        Fibo.push_back(Fibo[i - 1] + Fibo[i - 2]);
    }
    
    return Fibo[n];
}

Fibo라는 이름의 벡터에 맨 처음의 n -1과 n - 2, 즉 0번과 1번에 각각 1을 넣어주고 반복문을 돌린다. 이렇게 하면 Fibo에 저장한 이전 값들을 계속 활용할 수 있기 때문에 재귀 함수를 이용하여 스택에 접근하는 방식보다 상대적으로 빠를 것이다.
단순히 두 알고리즘만 놓고 봤을 때 시간을 분석하면 아래와 같이 나온다.



예상보다 시간차가 더 크게 나와 당황스럽지만 알고리즘을 잘 골라야하는 이유를 알 수 있다.
동적 계획법을 좀 더 효율적인 방식으로 만들 수 있다. 아래 코드를 보자.




3. 동적 계획법을 이용한 피보나치 수열 2



ull DP2_Fibo(int n){
    ull DP[3] = { 0, };
    DP[0] = 0;
    DP[1] = 1;
    int i = 2;
    while(i <= n){
        DP[2] = DP[0] + DP[1];
        DP[0] = DP[1];
        DP[1] = DP[2];
        i++;
    }
    
    return DP[2];
}

이번엔 배열을 이용해보았다. 핵심은 그게 아니라 DP라는 배열 3개만으로도 결과를 도출할 수 있다는 것이다. 일단 DP[2]에는 현재값을 저장하고 DP[1]에 있던 값을 DP[0]에 옮기고, DP[2]에 있는 현재값을 DP[1]에 옮김으로써 원래라면 DP[3]에 가야하는 값을 DP[0] + DP[1] (원래는 DP[1] + DP[2]의 값)을 연산하고 DP[2]에 다시 저장함으로써 저장공간을 극도로 아낄 수 있다. 단점은 2개의 값 말고 이전의 값들을 재활용 할 수 없다는 것이다. 이 경우 피보나치의 수열의 마지막 값을 구하고자 하는 것이 목표이기 때문에 이런 활용도 가능하다.
시간을 분석하면 아래와 같이 나온다.





소스코드 : https://github.com/betterafter/AlgoStudy/blob/master/main.cpp

댓글

댓글 쓰기