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

동적 계획법(Dynamic Programming) 이란?

---

동적 계획법이란 어떠한 문제에 대한 최적해를 얻고자할때 해당 문제에 대해 부분적으로 분할하여 작은 문제를 먼저 해결한 뒤, 각 부분에 대해 최적의 해답을 차례로 구해가는 알고리즘이다.

 

솔직히 이런 이론적인 어려운 말보다 내가 이해한 것을 말하자면 "분할 정복을 통해서 문제를 해결하는데 동일한 문제는 한번만 풀자" 이다.

 

단순 분할 정복은 동일한 문제를 반복적으로 계산해 시간을 낭비한다는 단점이 있다. 동적 계획법은 이러한 비효율적인 부분을 해결할 수 있다는 장점이 있다. 따라서 동적 계획법을 통해 문제를 해결하게 된다면 단일항 시간복잡도를 통해 문제를 해결할 수 있다.

 

 

위 사진은 피보나치 수열의 값을 재귀함수를 통해 구할 때 거치게되는 노드 트리이다. 여기서 확인할 수 있는 점은 반복된 함수를 여러번 호출한다는 것이다. 예를 들어서 F(1) 함수는 총 3번 호출하는데 이 결과는 항상 똑같다.

 

이렇게 동일한 문제를 여러번 풀게되면 그에 따라 낭비되는 시간이 존재하는데, 동적 계획법은 한번 푼 작은 문제의 결과를 배열에 기록(Memoization) 함으로써 이러한 문제를 해결한다.

 

LCS(Longest Common Subsequence)

---

동적 계획법을 사용해 해결할 수 있는 간단한 알고리즘을 보며 조금 더 구체적인 이야기를 해보려 한다. 그 알고리즘은 LCS(Longest Common Subsequence) 알고리즘이다. 원리는 간단하다 특정 숫자 배열에서 증가하는 가장 긴 부분 배열을 찾는 것이다. 예를 들면, {10, 20, 10, 30, 20, 50} 배열에서 {10, 20, 30, 50} 을 찾아내는 것이다.

 

우선 내가 문제를 풀면서 느꼈던 중요한 포인트는 "현재 내 상황이 될 수 있는 이전 상황에는 어떠한 것들이 있을까?" 를 생각하는 것이다. 

 

예를 들면, 위 배열에서 4번째인 30을 생각해보자, 30이 될 수 있는 이전 상황에는 10, 20, 10 세 개가 있을 수 있다는 것이다. 근데 복잡한 문제 들어가면 이러한 생각을 적용하기가 쉽지 않더라..ㅠ_ㅠ

 

이렇게 이전 상황에는 어떠한 것들이 있을지 생각해봤다면, "이 상황이 내 현재 상황이 되기 위해서는 어떤 과정을 거쳐야 하고 그 여러 가지의 결과중에 가장 올바른 값은 무엇일까?" 를 생각해야 한다. 올바른 값이라는 것은 위 문제에서는 최대 값이 될거고 특정 문제에서는 최소값이 될수도 있다.

 

백준 11053 LCS 문제 해답

 

사실 그냥 넘어간 포인트가 있는데 그건 위에서 계속 말했던 "상황"에 대한 것이다. 문제에서 현재 상황을 어떻게 표현할 것인지를 정해야 한다. 이 부분이 가장 어려우면서도 중요한 부분이다. 지금 소개하고 있는 LCS의 경우 현재 상황을 단순히 배열의 인덱스로 1차원으로 설정 됐지만 유명한 가방문제의 경우에는 2차원으로 접근해야 하는 경우도 있다. 이 것에 대한 연습이 많이 필요할 듯 하다.

 

요약하면,

1. 문제에서 "상황"을 어떻게 표현할지 정한다.
2. 현재 내 상황이 되기 직전의 상황에는 어떠한 것들이 있을 수 있는지 나열한다.
3. 나열한 직전의 상황에서 어떤 과정을 거쳐야 현재 상황이 될 수 있는지 나열한다.
   (이 과정을 점화식으로 표현할 수 있다면 더욱 베스트일 것 같다.)
4. 그 과정을 거쳐온 결과 중에 가장 올바른 값은 무엇인지 판단해 현재 상황의 결과 값으로 저장한다. 즉, 메모이제이션(Memoization) 한다는 것이다.

이러한 과정으로 생각할 수 있다. 사실 이건 정석 풀이가 아니고 그냥 내 생각이니까 각자의 풀이법을 고민해보는 것이 좋을 것 같다.

 

Bottom-up vs Top-down

---

동적 계획법으로 문제를 해결하는 방법으로는 Bottom-up 방식과 Top-down 방식이 있다. Top-down 방식은 흔히 재귀에서 사용되는 방식이라고 이해하면 좋다. 

 

Top-down 방식은 가장 큰 문제를 방문 후 작은 문제를 호출하여 답을 찾는 방식이고, Bottom-up 방식은 가장 작은 문제들부터 답을 구해가며 최종적인 문제의 답을 구하는 방식이다.

 

이에 대한 장단점은 아래 내용을 참고하자.

 

https://ggodong.tistory.com/211

 

동적 계획법을 해결할 때 Bottom-up 방식을 사용한다면 For문, Top-down 방식을 사용한다면 재귀함수가 등장하는 것이 일반적이다. 나는 For문을 이용한 Bottom-up 방식에 대해서 조금 더 편한 느낌인데 결국 둘다 할줄 알아야한다.

 

피보나치 문제를 해결하기 위한 두 가지 코드 예시를 살펴보자.

 

int fibonacci(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
 
    if (dp[n] != -1) return dp[n];
 
    dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return dp[n];
}

 

위 코드가 Top-down 방식을 이용한 해결 코드이다.

 

int fibonacci(int n)
{
    dp[0] = 0, dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
}

 

위 코드가 Bottom-up 방식을 이용한 해결 코드이다.