DP(Dynamic Programming)
(DP, 동적 계획법)은 탐욕 알고리즘(Greedy)과 함께 언급하는 알고리즘으로, 줄임말로 DP 라고 하는 이 알고리즘은, 탐욕 알고리즘과 같이 작은 문제에서 출발한다는 점은 같다. 그러나, 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, DP는 모든 경우의 수를 조합해 최적의 해법을 찾는다.
즉, 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결한다. 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 다시 말해, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍이다.
다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있다.
Overlapping Sub-problems: 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.Optimal Substructure: 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.
Overlapping Sub-problems
큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다.
이 가정의 대표적인 예시로 피보나치 수열을 들 수 있다.
피보나치 수열은 첫째와 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합과 같은 수열이다.
// 재귀함수로 구현한 피보나치 수열
function fib(n) {
if(n <= 2) {
return 1;
};
return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...
그림에서 본 것을 토대로, 7번째 피보나치 수 fib(7) 를 구하는 과정은 다음과 같다.
fib(7) = fib(6) + fib(5)
fib(7) = (fib(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)
...
피보나치 수열은 위 예시처럼 동일한 계산을 반복적으로 수행해야 한다.
이렇게, 작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때, 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족한다.
Optimal Substructure
이 조건에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미한다. 주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 한다. 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있다.
이 가정의 대표적인 예시로 최단 경로를 찾는 문제를 들 수 있다.
A에서 D로 가는 최단 경로를 찾아야 한다. 다음과 같이 각 지점이 있고, 한 지점에서 다른 지점으로 갈 수 있는 경로와 해당 경로의 거리는 다음과 같다.
A → D로 가는 최단 경로 : A → B → C → D
A → C로 가는 최단 경로 : A → B → C (A → B → E → C 가 아닙니다.)
A → B로 가는 최단 경로 : A → B
정리해보면 A에서 D로 가는 최단 경로는 그것의 작은 문제인 A에서 C로 가는 최단 경로, 그리고 한 번 더 작은 문제인 A에서 B로 가는 최단 경로의 파악할 수 있다. 이렇게 Dynamic Programming을 적용하기 위해서는, 작은 문제의 최적 해법을 결합하여 최종 문제의 최적 해법을 구할 수 있어야 한다.
Dynamic Programming - 피보나치 수열과 타일링
예제는 Dynamic Programming을 이용한 문제들이다. 해당 문제들과 이어지는 로직을 보고 분석해 보자.
Fibonacci
DP를 이용하여 피보나치 수열 문제를 해결하려고 할 때, 크게 두 가지 방식 Recursion + Memoization 과 Iteration + Tabulation 이 있다.
- Recursion + Memoization
: 다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해놓은 해결책을 이용한다. 이때 결과를 저장하는 방법을 Memoization이라고 한다.
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;
}다이내믹 프로그래밍을 적용한 피보나치 수열에서 fib(7)을 구하기 위해 fib(6)을, fib(6)을 구하기 위해 fib(5)을 호출한다. 이런 풀이 과정이 마치, 위에서 아래로 내려가는 것과 같다. 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식을 Top-down 방식이라 부르기도 한다.
Iteration + Tabulation
이번에는 반복문을 이용하여 다이내믹 프로그래밍을 구현한다.
Tabulation의 정의: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 제일 작은 값부터 구해 리스트(도표)에 작성함으로써 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
하위 문제의 결괏값을 배열에 저장하고, 필요할 때 조회하여 사용하는 것은 재귀 함수를 이용한 방법과 같다. 그러나 재귀 함수를 이용한 방법이 문제를 해결하기 위해 큰 문제부터 시작하여 작은 문제로 옮아가며 문제를 해결하였다면, 반복문을 이용한 방법은, 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법이다. 따라서 이 방식을 Bottom-up 방식이라 부르기도 한다.
function fibTab(n) {
if(n <= 2) {
return 1;
}
// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
let fibNum = [0, 1, 1];
for(let i = 3; i <= n; i++) {
fibNum[i] = fibNum[i-1] + fibNum[i-2];
// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
}
return fibNum[n];
}2x1 타일링
[ 문제 ]
2xn 크기의 타일이 주어진다면, 2x1과 1x2 크기의 타일로 채울 수 있는 경우의 수를 모두 구해야 한다.
n = 1일 땐 경우의 수는 1 : 세로 타일 1개
n = 2일 땐 경우의 수는 2 : 세로 타일 2개 or 가로 타일 2개
n = 3일 땐 경우의 수는 3 : 세로 타일 3개 or 왼쪽 세로 타일 1개 + 가로 타일 2개 or 가로 타일 2개 + 오른쪽 세로 타일 1개
2개의 타일로 빈 공간을 어떻게 채우든 상관없이, 맨 마지막 타일은 세로 타일 1개이거나 가로 타일 2개인, 2 가지 경우밖에 없다!!
맨 마지막 타일의 경우의 수를 제외했을 때 남는 공간의 마지막 타일도 세로 타일 1개, 혹은 가로 타일 2개인 2가지 경우밖에 없다. 이렇게, DP 문제는 문제 속의 규칙성을 찾는 것이 키 포인트dl다.
이렇게, DP 문제는 문제 속의 규칙성을 찾는 것이 키 포인트이다.
n = 4일 땐 경우의 수는 5 : 세로 타일 1개를 뺀 n = 3과, 가로 타일 2개를 뺀 n = 2일 때의 경우의 수
즉, 세로와 가로의 마지막 타일을 제외한 나머지 공간을 채우는 경우의 수와 답이 같다.
function tiling2x1(n) {
let memo = [0, 1, 2];
for (let i = 3; i <= n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n];
};금고 털기
function ocean(target, type) {
let bag = [1];
for(let i = 1; i <= target; i++)
bag[i] = 0;
for(let i = 0; i < type.length; i++) {
for(let j = 1; j <= target; j++)
if(type[i] <= j)
bag[j] += bag[j-type[i]];
}
return bag[target];
}크롬 개발자 도구에서 함수 실행 시간 측정 방법
함수의 실행 시간을 측정하는 방법은 여러 가지가 있다. 그중에서 다음의 방법으로 간단하게 함수의 실행 시간을 확인할 수 있다. 실행 환경에 따라 결과가 다르므로 측정 결과는 학습 용도로만 사용.
var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜라
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')