다이나믹 프로그래밍 1

---

'다이나믹 프로그래밍' 한글로 '동적 계획법' 이라는 알고리즘은 '리차드 벨만'이 만든 알고리즘 입니다.

리차드 벨만은 최단 경로를 찾는 '벨만 포드 알고리즘'도 만들었습니다.

​

​

1. 다이나믹 프로그래밍 이란?

데이터를 캐싱해 두고 이를 재사용 하므로써 중복된 연산을 피하기 위한 알고리즘 입니다.

​

​

2. 재귀 함수의 이슈

피보나치 수열은 다음과 같습니다.

정리하면 다음과 같은 조건식 입니다.

1. f(1) = f(2) = 1                [base case]

2. f(n) = f(n-1) + f(n-2)   [general case]

​

​

3. 피보나치 수열 재귀함수로 구현

피보나치를 구현하는 가장 단순한 방법은 재귀 함수를 사용하는 방법 입니다.

int fib(int n){
    if(n == 1 || n == 2)
        return 1;
    else
        return fib(n-2) + fib(n-1);
}

그런데, 재귀함수를 사용하면 문제점이 있습니다.

이와 같이 재귀함수로 피보나치 수열을 구현한 경우 중복되는 연산이 발생 합니다.

​

​

2. Memoization 을 이용한 중복 연산 없애기

Memoization은 연산을 통해 얻은 데이터를 메모리에 저장 하고 있다가 사용 하는 방법으로 반복 되는 연산을 제거하여 실행 속도를 높이기 위해 사용 됩니다.

// memoization 배열의 값을 모두 -1로 초기화
for(from 0 to n){
    memoization[n] = -1;
}

int fib(int n){
    if(n==1 || n==2)
        return 1;
    else if(memoization[n] != -1) // memoization 배열은 -1로 초기화 되어 있습니다.
        return memoization[n];    // 즉 이미 memoization배열의 값이 저장 되어 있다면 저장되어 있는 값을 반환 합니다.
    else{
        memoization[n] = fib(n-2) + fib(n-1);
        return memoization[n];
    }         
}

memoization 라는 배열을 -1로 모든 데이터를 초기화 해주고, 값이 -1 이라면 피보나치 수열을 계산하고, -1이 아니라면 메모리에 저장 되어있는 데이터를 반환해 줍니다. 이로써 중복되는 연산을 피할수 있습니다.

 

 

3. bottom-up 방식으로 중복된 연산 없애기

위에서 소개한 방식은 재귀 함수의 base case의 수렴 해야 하기 때문에 top-down 방식이라고 할 수 있습니다. 하지만, 반복문을 사용하여 작은수 부터 큰수 까지 bottom-up 방식으로 피보나치 값을 구할 수 있습니다.

int fib(int n){
   memoization[1] = memoization[2] = 1;
   for(int i=3; i<=n; i++)
       memoization[n] = memoization[n-1] + memoization[n-2];
   return memoization[n];
}

위 방법 또한 memoization 배열에 순차적으로 필요한 값을 넣어놓고 읽어와 사용하여, 중복된 연산을 피할수 있습니다. 위의 재귀 함수를 이용한 memoization 방식과 반복문을 이용한 memoization 방식 모두 '동적 계획법' 또는 '다이나믹 프로그래밍' 또는 이를 줄여서 'DP' 라고 부릅니다.

 

​

정리

메모리제이션, 동적 계획법은

1. 실제로 필요한 작은 문제만을 풀어 큰 문제를 구하는 방법 입니다.

2. 데이터를 기억하고 있다가 중복된 연산이 발생하면 데이터를 읽어 사용 합니다.