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

다이나믹 프로그래밍이란

• dynamic programming은 최적의 답을 찾기 위한 수학적인 개념으로 복잡한 문제를 간단한 문제의 sequence로 변형해 풀이하는 divide and conquer 최적화 방법 중 하나이다.
• divide and conquer 방법의 단점은 동일한 계산을 반복해서 수행해야하는 단점이 있는데 중간 계산 결과를 저장해 한 번만 계산하도록 하는 memoization으로 이 문제를 극복합니다.
• dynamic programming을 적용할 수 있는 문제는 '최적성 원리'가 성립하는 문제다. 최적성의 원리는 문제 전체의 최적해가 작은 부분의 최적해로 구성될 때 성립한다. 이 경우 문제를 점화식 형태로 구성해 풀이한다.

피보나치 수열

• 피보나치 수열은 첫 두 항이 1로 시작하고, 연속된 두 항의 합이 다음 항의 값이 되는 수열이다.

1항	2항	3항	4항	5항	6항	7항	8항
1	1	2	3	5	8	13	21

• 피보나치 수열은 명시적인 일반항을 정의할 수 없고 항 간의 관계로 점화식을 정의해 표현할 수 있다. 연속된 두 항의 합이 그 다음 항의 값이 된다는 말을 점화식으로 표현하면 다음과 같이 표현할 수 있다.

$$ f[n] = f[n-1] + f[n-2]$$

• 반복적인 계산으로 피보나치 수열의 임의의 항의 값을 계산할 수 있다. 재귀 함수를 통해 피보나치 수열의 임의의 항을 계산한다고 하면 명시적으로 값을 정의한 제 1항과 제 2항이 나올 때 까지 점화식을 활용해 치환해 나가야한다.
• 예를 들어 $f[5]$의 값을 구하고자 할 때 점화식을 사용하면 $f[4]$와 $f[3]$의 값을 계산해야한다.
• $f[3]$은 $f[2] + f[1]$로 바로 2로 계산할 수 있지만, $f[4]$는 $f[3] +f[2]$로 전개되어 $f[3]$을 다시 한번 계산해야한다. $f[5]$를 재귀적으로 계산하는 과정은 아래 그림과 같다.

재귀 함수 활용 피보나치 수열 계산

• $f[5]$를 구할 때 까지 $f[3]$은 중복되어 계산된다. 만약 구하고자 하는 항이 커질 수록 중복되는 계산의 수가 급격히 늘어나 비효율적이다.
• 이때 피보나치 수열의 중간 계산 값을 저장하고 이후에 그 값을 활용하면 비용을 줄일 수 있다. 정의가 되어있는 1항과 2항을 제외하고 3항부터 계산한 값을 다른 공간에 저장을 하고 다음번 해당 값이 필요할 때 그 값을 다시 계산하는 것이 아니라 저장된 값을 읽어오는 방식으로 계산 비용을 줄일 수 있다.

memoization 적용 피보나치 수열 계산

• 아래 코드에서 line 22의 n값을 바꾸며 확인해보면 실행시간의 차이를 확인할 수 있다. n이 커짐에 따라 소요 시간의 차이가 커지고 있다.

피보나치 수열의 n항을 구하는데 소요되는 시간

Dynamic programming을 구성하는 요소

Stages

• DP를 적용하기 위해서는 문제를 multipple stage로 구성하는 것이 필요하다.
• 하나의 stage는 일반적인 최적화 방법으로 해결할 수 있어야 하고, 이 결과는 다음 stage의 최적화에 도움을 준다.
• 시간에 따라 정의되는 stage는 순서가 명확하지만 종종 시간의 의미를 포함하지 않는 경우 Stage의 순서를 정의하는 것이 어려울 수 있다.
• 위의 피보나치 수열의 예시에서는 각각의 수열의 항이 stage가 된다.

State

• State는 각 stage를 설명하는 변수로 해당 stage에 도달하는 과정에 대한 정보를 모두 포함한다.
• 다음 stage의 state를 구할 때는 현재 state값만 넘겨주면 그 stage까지 과정을 생략하고 다음 state 값을 구할 수 있다.
• 위의 피보나치 수열의 예시에서는 수열의 항의 값이 state가 된다.

Decision

• 한 state에서 다음 state로 전환할 때 선택할 수 있는 state가 다수라면 그 중 하나를 선택해야 한다.
• 위의 피보나치 수열의 예시는 state가 전환할 때 선택지가 하나 뿐이기 때문에 decision은 고려하지 않는다.

점화식 표현

• dynamic programming을 구성요소로 표현하면 다음과 같이 표현할 수 있다.
• $s[n]$는 n번째 stage의 state, $d[n]$ n번째 stage의 decision이라고 하면 dynamic programming은 다음과 같이 정의할 수 있다.
  $$s[n] = f(s[n-i], d[n-j])$$
• dynamic programming 방식으로 문제를 해결하고자 할 때 stage, state, decision을 정의하는 것이 창의적인 아이디어가 필요한 부분이다.

Examples

투자의 귀재 배주형

• 이 문제는 dynamic programming의 구성 요소를 모두 포함하면서 어렵지 않게 풀 수 있어 dynamic programming의 개념을 익히기에 적합한 문제라고 생각한다.
• n년의 최대 수익은 1)A투자로 n-1년 최대 수익에 5%, 2)B투자로 n-3년 최대 수익에 20%, 3)C투자로 n-5년 최대 수익에 35%을 더한 값 중 가장 큰 값이 된다. 이로부터 최적성의 원리 조건을 만족하는 것을 확인하고 dynamic programming 방식으로 풀이하면 된다.
• stage는 시간($t$)으로 정의할 수 있고, state($DP$)는 해당 년도에 얻을 수 있는 최대 수익, decision은 투자의 종류를 결정하는 것으로 정의한다. 이를 점화식 형태로 나타내면 다음과 같다.

$$DP[t] = max(투자 A, 투자 B, 투자 C)$$

• dynamic programming으로 문제를 정의한 후 코드로 구현하는 것은 어렵지 않게 구현할 수 있다.

같이 풀어보면 좋은 문제들

2022.08.05 - [알고리즘 공부/백준 문제풀이] - [백준 python] 14501번 퇴사

2022.09.05 - [알고리즘 공부/백준 문제풀이] - [python 백준] 1463번 1로 만들기