Dynamic Programming란? (동적 계획법)
- 하나의 큰 문제를 여러 개의 작은 문제로 나눠서 그 결과를 저장해 다시 큰 문제를 해결할 때 사용
- 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
- 특정 알고리즘이 아닌 하나의 문제해결 패러다임
- 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 함
- "기억하며 풀기" 라고도 불림
DP를 사용하는 이유
- 일반적인 재귀 방식과 매우 유사함
- 큰 차이점 : 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될 수 있음
ex) 피보나치 수열
간단한 재귀함수(return f(n) = f(n-1) + f(n-2))
DP 만족 조건
1. 최적 부분 구조 (Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우2. 중복되는 부분 문제 (Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결해야 하는 경우DP 사용하기
-
DP로 풀 수 있는 문제인지 확인
특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산
-
문제의 변수 파악
현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용.
→ 문제 내 변수의 개수를 알아야 함 -
변수 간 관계식 만들기 (점화식)
짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축해줌
-
메모하기 (memorization or tabulation)
변수의 값에 따른 결과 저장 → 재사용
-
기저 상태 파악하기
가장 작은 문제의 상태를 알아야 함.
-
구현하기
Top-Down (Memorization 방식) - 재귀 사용
Bottom-up (Tabulation 방식) - 반복문 사용
Top-Down
- 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식 (하향식)
- 점화식을 이해하기 쉽다
dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용
가장 최근의 상태 값을 메모해 두었다고 하여 Memoization이라고 부른다.
- ex) 피보나치 Top-Down
function fib(n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}Bottom-Up
- 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식 (상향식)
- 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결
- 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다
dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 할 때,
Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식
반복을 통해 dp[0]부터 하나 하나씩 채우는 과정 → "table-filling"
Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation 이라고 불림
→ 근본적인 개념은 Memoriztaion과 크게 다르지 않다.
- ex) 피보나치 Bottom-Up
function fib(n) {
const result = [0, 1];
for (let i = 2; i <= n; i++) {
const a = result[i - 1];
const b = result[i - 2];
result.push(a + b);
}
return result[n];
}