[알고리즘] 다이나믹 프로그래밍 (DP)

다이나믹 프로그래밍

다이나믹 프로그래밍이란 어떤 문제를 해결하는 것에 있어, 중복적인 계산을 최대한 피하는 방법이다. (2*5) + (2*6)의 문제를 해결할 때를 생각해보자. (2*5)만 알면 (2*6)은 (2*5 + 2)로 해결할 수 있다. 따로 (2*5)를 또 계산할 필요가 없이 미리 해결한 (2*5)의 결과값을 이용한 것이다. 이것이 다이나믹 프로그램의 핵심이다. 문제가 더더욱 복잡하고 중복되는 계산이 많은 상황에서는 여러 계산과정을 생략할 수 있어 유용할 것이다. 좀 더 자세히 살펴보자.

---

다이내믹 프로그래밍의 조건

 

1. 최적 부분 구조 : 부분 문제의 최적의 답을 통해 상위문제(기존문제)의 최적의 답을 구할 수 있다.

 

ex. 피보나치 수, fib(n) = fib(n -1) + fib(n - 2)

-> fib(n-1)과 fib(n-2)라는 부분문제의 최적을 답을 통해 현재의 값을 구할 수 있다.

 

2. 중복되는 부분 문제 : 말그대로 부분 문제 중에 중복되는 부분이 있어야 한다.

 

ex. fib(5) = fib(4) + fib(3) = fib(3) + fib(2) + fib(3) = fib(3) + fib(2) + fib(2) + fib(1)

-> 내부적으로 fib(3)이나 fib(2), fib(1)를 중복적으로 활용하고 있음을 알 수 있다. (반면 합병 정렬 같은 과정은 최적 부분 구조를 가지고 있지만, 각 부분 문제 내부에 중복되는 부분이 존재하지 않는다.)

---

다이나믹 프로그래밍의 방식 : Memoization

 

말 그대로 따로 메모를 하는 방식이다. 부분 문제에 대한 답을 저장해놓고, 나중에 또 그 부분 문제에 대한 답이 요구되는 상황이 오면 또 계산하지 않고 저장해놓은 값을 불러온다. 부분 문제에 대한 답을 저장해놓는 공간을 흔히 cache라고 한다.

 

memization 방식은 문제를 해결할 때 위에서부터 아래로 내려온다. 이를 Top-down-approach이라고 한다. 즉, 부분 문제를 제일 아래까지 찾다가 더 이상 부분 문제가 없는 base-case에 도달하면 거기부터 '계산-답 저장-중복 문제는 저장된 값에서 불러오기'의 과정을 반복한다는 것이다.

 

주로 재귀를 활용한다.

---

다이나믹 프로그래밍의 방식 : Tabulation

 

테이블을 그려놓고 하나씩 진행하며 저장하는 방식이다. 제일 최소의 단위부터 문제의 값을 테이블에 저장해 나가며, 제시된 문제를 해결할 수 있으면 거기서 해당 값을 리턴한다. 

 

tabulation 방식을 문제를 해결할 때 아래에서부터 위로 올라간다. 이를 Bottom-up-approach라고 한다. 

 

주로 반복문을 활용한다.

---

Memoization vs Tabulation

 

Memoization은 재귀를 활용하기 때문에 재귀의 자체적문제(stack_error)가 발생할 수 있다. 하지만 Tubulation은 반복문을 활용하기 때문에 그럴 위험이 적다. 

 

하지만 Tabulation은 처음부터 계산해 올라가는 것이기 때문에 필요없는 부분까지 모두 계산할 수도 있다는 단점이 있지만, Memoizaion은 필요한 것만 찾아서 계산해오는 방식이기 때문에 좀 더 효율적일 수 있다.

---

다이나믹 프로그래밍의 공간 최적화

 

앞서 언급한 Memoization과 Tabulation 모두 현재까지 찾은 값을 모두 저장해놓는다. 하지만 조금 생각해보면, 이는 매우 비효율적임을 알 수 있다. 피보나치수열 계산을 생각해보자. N의 피보나치 수 계산에서 필요한 것은 N-1의 피보나치 수와 N-2의 피보나치 수뿐이다. 따라서 값을 모두 저장해놓는 것은 공간적으로 보았을 때 매우 비효율적이라고 할 수 있다. 따라서 필요한 값들만 그때 그때 저장하는 방식을 활용해 공간을 최적화해줄 필요가 있다.