[Kotlin] 동적 계획법 (Dynamic Programming, DP) (+ 분할 정복과의 차이)

1. 동적 계획법(Dynamic Programming, DP)

 

주어진 문제를 작은 문제로 나누어 푸는 알고리즘.

작은 문제를 해결한 후, 해결한 작은 문제의 해답을 활용하여 주어진 문제를 해결하는 방식을 말한다.

 

피보나치 수열을 해결 할 때 f(n) = f(n-1) + f(n-2) 와 같은 점화식을 가지게 되는데,

이는 f(n)을 구하기 위한 하위 문제들 (f(n-1), f(n-2)..) 의 해가 중복된다.

 

 

f(6)을 구하기 위해 중복 사용되는 하위 문제들의 해

 

f(6)을 구하기 위해 하위 문제들의 해를 중복으로 구하게 됨으로써, 비효율적인 시간 복잡도를 가지게 된다.

 

이렇게 답을 구하기 위해 했던 계산을 반복해야 하는 문제에서 하위 문제의 해를 재사용해 문제를 해결하는 DP가 효율적으로 동작한다.

 

2. 동적 계획법의 조건

최적 부분 구조(Optimal Substructure)를 가지는 중복된 하위 문제들(Overlapping Subproblems)이 존재하는 문제일 때

DP를 통해 해결 할 수 있다.

 

 

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

문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 구조를 말한다.

 

예를 들어, 서울에서 부산까지 가는 최적 경로를 구한다고 가정하자.

이 때, 서울 -> 대구 -> 부산이 최적 경로의 해답이라고 한다면,

각 부분 문제인 서울 -> 대구 와 대구 -> 부산의 해가 합쳐져 주어진 문제에 대해 서울 -> 대구 -> 부산의 해가 나오는 것이다.

 

이를 피보나치 수열에 적용한다면 다음과 같다.

 

주어진 문제 : N번째 피보나치 수를 구한다.

부분 문제 : N-1번째 피보나치 수를 구한다, N-2번째 피보나치 수를 구한다.

주어진 문제의 해답 : 부분문제(N-1번째 피보나치 수, N-2번째 피보나치 수)의 해를 합친다.

 

주어진 문제 : N-1번째 피보나치 수를 구한다.

부분 문제 : N-2번째 피보나치 수를 구한다, N-3번째  피보나치 수를 구한다.

주어진 문제의 해답 : 부분문제(N-2번째 피보나치 수, N-3번째 피보나치 수)의 해를 합친다.

 

...

 

2-2. 중복된 하위 문제들(Overlapping Subproblems)

주어진 문제가 여러 부분 문제로 나누어 질 수 있는 문제를 말한다.

즉, 부분 문제가 중복되지 않아 부분 문제마다 새로운 연산을 수행해야 하는 것이 아니라

같은 부분 문제가 다른 부분 문제에 재사용 될 수 있는, 말 그대로 '중복'되는 부분 문제를 가지는 경우를 말한다.

 

이 역시도 피보나치 수열에 적용하면 다음과 같다.

 

주어진 문제 : N번째 피보나치 수를 구한다.

부분 문제 : N-1번째 피보나치 수를 구한다, N-2번째 피보나치 수를 구한다.

 

파생된 부분 문제 : N-1번째 피보나치 수를 구한다.

부분 문제 : N-2번째 피보나치 수를 구한다, N-3번째  피보나치 수를 구한다.

 

...

 

이러한 부분 문제가 계속 이어짐으로써, 위와 같이 N-m번 째 피보나치 수를 구하는 부분 문제가 중복된다.

 

 

3. 메모이제이션(Memoization) 

Optimal Substructure 구조를 만족하는 DP의 특징에 의해 부분 문제의 해는 늘 같은 값을 가지며,

Overlapping Subproblems를 만족하는 DP의 특징에 의해 부분 문제는 다른 부분 문제에 재사용된다.

 

이렇게 주어진 문제를 위해 '같은 값을 가지고 재사용' 되는 부분 문제의 해를 저장하기 위해

DP는 메모이제이션(Memoization) 방식을 사용한다.

 

메모이제이션이란,

부분 문제의 해를 구했을 때 변하지 않는 해에 대해 중복된 연산을 수행하지 않기 위해 그 해를 cache에 메모하는 것을 말한다.

 

코드에서는 일반적으로 배열에 해를 저장한다.

 

먼저, 메모이제이션을 사용하지 않는 피보나치 수를 구하는 함수를 본다.

 

fun fib(num: Int): Int {
    if (num <= 1) return num
    return fib(num-1) + fib(num-2)
}

fib(5)를 구한다고 할 때, fib(4) + fib(3)을 return 한다.

fib(4)는 다시 fib(3)과 fib(2)를 return하고,

fib(3)은 다시 fib(2)와 fib(1)을 return하고 ...

이미 구한 해에 대해서 또다시 해를 구하기 위한 함수를 수행한다.

 

 

이를 최적화하기 위해 메모이제이션을 사용하여 피보나치 수를 구하는 함수를 본다.

 

val cache = Array(100) { 0 }
fun fib(num: Int): Int {
    if (num <= 1) return num

    if (cache[num] > 0) {
        return cache[num]
    }

    cache[num] = fib(num-1) + fib(num-2)
    return cache[num]
}

 

이미 구한 해를 저장 할 수 있는 cache 배열을 만든다.

만약 cache[num]의 값이 존재한다면 재귀 함수를 호출하지 않고 즉시 저장되어 있는 해를 return 하고,

값이 저장되어 있지 않다면(= 해가 계산되지 않았다면) 그 때 해를 계산하는 재귀함수를 호출하고

이를 cache[num]에 저장하여 재사용 할 수 있도록 한다.

 

 

 

 

4. 분할 정복(Divide and Conquer) 과의 차이점

분할 정복 역시 주어진 문제를 작은 문제로 나누어 해결하는 알고리즘이므로 비슷하다고 느낄 수 있다.

그러나 DP는 부분 문제가 주어진 문제를 해결하는 방식으로 중복되어 해를 재사용 할 수 있지만,

분할 정복은 작은 문제가 절대 중복 될 수 없다. 그러므로 분할 정복에서는 메모이제이션 방식을 사용 할 수 없다.

 

위에서 예시로 든 피보나치 수열의 경우 주어진 문제의 부분 문제가 같은 점화식 (f(n) = f(n-1) + f(n-2))을 가진다.

이러한 이유로 주어진 문제를 작은 문제로 나누어 해결하는 매커니즘은 비슷하다 하더라도

피보나치 수열과 같은 문제에서는 작은 문제 간 해가 중복될 수 없는 분할 정복보다는 DP가 효율적인 것이다.

 

 

참고 : https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95#s-2.3

 

https://ansohxxn.github.io/algorithm/dp/

(C++) 동적 계획법 Dynamic Programming

 

https://velog.io/@polynomeer/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

동적 계획법(Dynamic Programming)