동적 계획법 (Dynamic Programming)

1. 동적 계획법이란?

하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 방법이다.

알고리즘이 아닌 하나의 문제 해결 방법으로 볼 수 있다.

예를 들어, 피보나치 수열을 일반적인 재귀로 구하려면, 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 된다.

동적 계획법으로 한번 구한 작은 문제의 결과 값을 저장하고 재사용한다면, 시간복잡도가 대폭 줄어들게 된다.

 

2. 사용 조건

2가지 조건을 만족해야 한다.

1. Overlapping Subproblems  ( 겹치는 부분 문제)
   DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용하여 전체 문제의 답을 구한다.
   그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
2. Optimal Substructure  ( 최적 부분 구조 )
   부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다.
   그래서 특정 문제의 답은 문제의 크기에 상관없이 항상 동일하다.
   
   

3. 사용하기

1. DP로 풀 수 있는 문제인지 확인한다.
   
   위의 사용 조건이 충족되는지 체크한다.
   
   
2. 문제의 변수 파악
   
   문제 내 변수의 개수를 알아내야 한다.
   
   
3. 변수 간 관계식 만들기
   
   반복 혹은 재귀를 통해 문제가 자동으로 해결되도록 구축한다.
   
   
4. 메모하기 ( Memoization)
   
   변수의 값에 따른 결과를 저장한다.
   변수 값에 따른 결과가 나올 때마다 저장하고, 저장된 값을 재사용한다.
   보통 배열에 저장을 하며, 변수의 개수에 따라 배열의 차원이 다양할 수 있다.
   
   
5. 기저 상태 파악하기
   
   가장 작은 문제의 상태를 알아야 한다.
   해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 된다.
   
   
6. 구현하기
   
   두 가지 방식으로 구현할 수 있다.
   
   [ Bottom-Up (Tabulation 방식) - 반복문 사용 ]
   아래에서부터 계산을 수행하고 누적 시켜서 전체 큰 문제를 해결하는 방식이다.
   dp[0]이 기저 상태이고 dp[n]이 목표 상태이다.
   
   [ Top-Down (Memoization 방식) - 재귀 사용 ]
   위에서부터 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.