모든 경우의 수를 조합해 최적의 해법을 찾는 방식
주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해겳 방식
하나의 문제는 단 한번만 풀도록 하는 알고리즘
두가지 조건이 만족해야 DP를 사용할 수 있다.
•
큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견됨 (Overlapping Sub-problems)
•
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같음
→ 즉 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있음 (Optimal Substructure)
Memorization
하위 문제를 해결할 때, 그 해결책을 저장해 두고 똑같은 문제가 발생했을 때 저장되어 있던 해결책을 가지고 활용하는 방식으로 중복 계산을 줄이는 방법
동적계획법에서 각 문제는 한 번만 풀어야함. 정답을 한번 구했으면 그 정답을 메모해놓는다.
동적 계획법 구현 방식
1. Top-down
큰 문제를 작은 문제로 쪼개면서 푼다
재귀로 구현
1.
큰 문제를 작은 문제로 나눈다
2.
작은 문제를 푼다
3.
작은 문제를 풀었으니, 이제 큰 문제를 푼다.
ex)
function fibMemo(n, memo = []) {
// 이미 해결한 하위 문제인지 찾아본다
if(memo[n] !== undefined) return memo[n];
if(n <= 2) return 1;
// 없다면 재귀로 결괏값을 도출하여 res 에 할당
let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
memo[n] = res;
return res;
}
JavaScript
복사
2. Bottom-up
작은 문제부터 차례대로 푼다
반복문으로 구현
1.
문제를 크기가 작은 문제부터 차례대로 푼다.
2.
문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.
3.
작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
4.
반복하다 보면 가장 큰 문제를 풀 수 있다
ex)
function fibTab(n) {
if(n <= 2) return 1;
let fibNum = [0, 1, 1];
// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
for(let i = 3; i <= n; i++) {
fibNum[i] = fibNum[i-1] + fibNum[i-2];
// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
}
return fibNum[n];
}
JavaScript
복사