[ Algorithm ] 동적 계획법

동적 계획법 ( Dynamic Programming ) 

 : 하나의 복잡한 문제를 한번에 해결하는 것이 아닌 여러 개의 작은 문제로 나눠 큰 문제를 점차적으로 해결할 때 사용한다

   -> 점화식을 이용해 문제를 풀어나간다고 생각하면 된다.

 

동적 계산법 사용 조건

1. Overlapping Subproblems (중복되는 부분 문제)

DP는 기본적으로 큰 문제를 나누고 여러 부분 문제로 나눠지며 부분 문제들이 중복해서 나타난다.  

하지만 DP는 부분 문제의 결과를 저장하여 계산이 되어야하지만 부분 문제가 중복으로 나타나지 않아 재사용이 불가능한 경우 DP(동적계산법)을 사용할 수 없다.

 

2. Optimal Substructure(최적 부분 구조)

부분 문제의 최적의 값을 이용해 큰 문제에 영향을 받지 않고 항상 동일한 값을 나타낸다.

즉, 큰 문제의 해는 부분 문제의 조합으로 찾을 수 있으며 동일한 연산으로 수행한다.

 

피보나치 수열의 식을 예로 들 수 있다.

fibo(n) = fibo(n - 1) + fibo(n - 2)

fibo(n)의 답을 얻기 위해 작은 부분인 fibo(n - 1) , fibo(n - 2)이 최적의 값이 이어야한다. 

fibo(n - 1)을 구하기 위해 fibo(n - 1) =  fibo(n - 2) + fibo(n - 3)을 사용하고 fibo(n - 2)의 값이 중복된다.

 

최적 부분 구조를 가지게 된다면 fibo(n - 1)은 크기와 상관없이 동일한 값을 가진다는 것을 확인 할 수 있다.

 

만약 재귀함수로 풀면 중복 부분을 1번씩 호출하면 동일한 값을 2번씩 구하기 때문에 호출되는 함수 횟수 또한 기하급수적으로 증가한다. 이때의 시간복작도는 O(2ⁿ) 이다. 이러한 중복 연산과정을 줄이고 재사용하는 방법은 무엇이 있을까? 

이는 Memoization(메모이제이션) 개념을 말 할 수 있다.

 

Memoization(메모이제이션) 

 : 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행속도를 빠르게 해주는 기법 - 위키백과

 메모리에 이전에 계산된 값을 저장함으로써 반복 수행할 때 연산없이 저장된 값을 사용한다는 것을 말한다.

 

피보나치 수열의 예로

fibo(4) = fibo(3) + fibo(2)
 - fibo(4) = (fibo(2) + fibo(1) + fibo(2)

fibo(2)의 해를 메모리에 저장하면 fibo(2)의 값은 따로 풀지 않아 O(n)의 시간복잡도를 가지게 된다.

 

동적 계산법 접근 방법 

◻️ Bottom-Up

◻️ Top-Down

 

🔹 Bottom-Up 방법

 : 아래서 위로 접근하는 방법

 : 작은 문제에서부터 문제를 해결하여 점차 큰 문제를 풀어 가는 방식

 : 반복문을 사용하는 방법

int main()
{
    int N;
    vector<int> D;
    cin >> N;
    
    for(int i = 0; i <= N; i++)
    {
    	D[i] = -1;
    }
    
    D[0] = 0;
    D[1] = 1;
    
    for(int i =2; i <= N; i++
    {
    	D[i] = D[i - 1] + D[i - 2];
    }
}

 

🔹 Top-Down 방법

 : 위에서 아래로 접근하는 방법

 : 큰 문제에서 부분 문제로 나눠 문제를 풀어 가는 방식

 : 코드의 가독성이 좋고, 이해하기 편하다.

 : 재귀 함수을 사용하는 방법

int main()
{
    int N;
    vector<int> D;
    cin >> N;
    
    for(int i = 0; i <= N; i++)
    {
    	D[i] = -1;
    }
    
    D[0] = 0;
    D[1] = 1;
    
    fibo(N);
}

fibo(int n)
{
    if(D[n] != -1)
    {
    	return D[n];
    }
    
    return D[n] = fibo(n - 2) + fibo( n - 1 ); //테이블에 저장 후 반환
}

 

⭐ 참고 자료

https://hongjw1938.tistory.com/47

https://didu-story.tistory.com/220