Dynamic Programming (동적 계획법)
1. 개요
동적 계획법 이라는 거창한 이름과 다르게 동적(Dynamic)과 크게 관련은 없다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 하는 알고리즘이며 기억하여 풀기 라고도 한다.
2.사용 이유
보통 비효율적인 반복되는 계산을 방지하기 위해 사용한다.
가장 유명한 예시인 피보나치 수열을 예로 들 수 있다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
다음과 같은 피보나치 수열을 재귀함수로 나타내면
f(n) = f(n-1) + f(n-2)
이라는 어렵지 않은 점화식을 구할 수 있다.
하지만 n이 커짐에 따라 함수f의 호출횟수가 기하급수적으로 커진다.
즉, 비효율적인 반복되는 계산이 생기고 있다.
이를 그림으로 본다면 다음과 같다.
이 때 한번 구한 문제의 결과값들을 따로 저장해 둔다면 이미 계산해놓은 함수값들을 다시 계산하는 비효율적인 반복되는 계산을 막을 수 있다.
3. 사용조건
-
Overlapping Subproblems(겹치는 부분 문제)
-
Optimal Substructure(최적 부분 구조)
1️⃣ Overlapping Subproblems
DP는 기본적으로 동일한 작은 문제들이 반복하여 나타나는 경우에 사용가능하다.
즉, 분할과 정복(Divide and conquer)과 비슷하다.
분할및 정복과 다른 점은 메모지에이션(Memoization) or DP테이블 을 사용한다는 점이다.
위에서 본 피보나치 수열과 같이 이미 계산한 결과는 배열에 저장 해 두면 최적의 효율을 가질 때 dp를 이용한다.
2️⃣ Optimal Substructure
부분 문제의 최적 구조를 이용해 최적의 결과를 내는 경우를 말한다.
쉽게 말하면 동일한 작은 문제를 반복적으로 해결하는 구조 인 경우를 말한다.
이 때 주의할 점은 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않아야 한다.
4. Problem solving 에서의 DP
일반적으로 dp문제를 풀 때 다음과 같은 순서로 생각한다.
**1. DP로 풀어야 하는 문제인지 확인한다.
- 점화식 만들기
- 메모하기
- 기저상태 확인하기
-
구현하기**
DP로 풀어야 하는 문제인지 확인한다
가장 중요한 부분중에 하나이다. dp를 처음부터 생각하고 문제를 임하는 것 보다 문제를 해결하기 위해 접근했을 때 위에서 본 사용 조건을 만족하면 dp를 이용하는 것을 고려해 볼 만 하다.
보통 최단 경로 문제 , 데이터의 최대화/최소화, 확률계산 등에 사용하는 경우가 많다.
점화식 만들기
예를 들어 피보나치 수열에서 f(n) = f(n-1) + f(n-2) 와 같은 점화식을 얻어낼 수 있다면, 코드 내에서 반복/재귀를 이용해 문제 해결할 수 있다. 점화식은 변수의 개수와 문제의 상황에 따라 다르며 점화식을 만들어 내는데 보통 가장 많은 시간을 쓴다.
메모하기
변수의 값에 따른 결과값을 저장하는 과정이며 후술할 하향식(Top-down), 상향식(Bottom-up)에 따라 memoization, Tabulation을 이용해 문제를 해결해 나간다. 결과 값을 이용할 때는 변수의 개수에 따라 배열의 차원이 다르다.
기저상태 확인하기
피보나치 수열에서 f(0), f(1) = 1 이라는 기저상태가 없다면 피보나치 수열의 점화식 만으로는 f(n)의 값을 알 수 없다.
이처럼 가장 작은 문제 상태를 알아야 문제를 해결 할 수 있다.
구현하기
dp의 구현에는 2가지 방식이 있다.
**1. 상향식(Bottom-up) - 반복문 사용
- 하향식(Top-down) - 재귀 사용**
구현방식
- 상향식(Bottom-up)
아래부터 연산을 수행하고 결과값을 누적시키서 목표하는 값을 구하는 방식이다.
이 때 Tabulation을 이용한다.
예를 들어 dp[n]이 구하는 목표이면 dp[0]부터 반복문을 이용해 이전 결과값들을 이용해 dp[n]을 구하는 방식이다.
- 하향식(Top-down)
앞서 본 상향식과 다르게 하향식은 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]상태까지 내려간 다음 그 결과를 재귀를 통해 전이시켜 재활용한다.
결과를 재활용할 때 반복되는 결과값을 매번 구하지 않고 메모해두고 필요할때 메모해둔 것을 사용한다 해서
memoization 을 사용한다고 한다.
상향식은 하향식에 비해 Stack Overflow에 자유롭고, 하향식은 코드가 더 이해하기 쉽다는 장점이 있다.