앞서 배운 탐욕 알고리즘과 늘 함께 언급되는 알고리즘으로 Dynamic Programming(동적 계획법)이 있습니다. 탐욕 알고리즘과 다이내믹 프로그래밍 모두 작은 문제에서부터 출발한다는 점은 같지만, 탐욕 알고리즘이 순간의 최적을 찾는 방식이라면, 이번 시간에 배울 Dynamic Programming은 모든 경우의 수를 따져본 후 이를 조합해 최적의 해법을 찾는 방식입니다.
Dynamic Programming의 원리는 간단합니다. 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식입니다. 하위 문제를 계산한 뒤 그 해결책을 저장하여, 후에 같은 하위 문제가 나왔을 경우 저장된 해결책을 이용하여 계산 횟수를 줄임으로써 비효율적인 알고리즘을 개선하는 방법입니다. 즉, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍입니다.
다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있습니다.
1. 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다. (Overlapping Sub-problems)
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (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(6) = fib(5) + fib(4)
fib(5) = 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 → B → C → D 라는 것을 간단하게 생각해 낼 수 있습니다. 그렇다면 A에서 C로 가는 최단 경로는 어떨까요? A → B → E → C가 아닌 A → B → C 라는 것을 알 수 있습니다. 마지막으로 A에서 B로 가는 최단 경로는? 당연히 A → B이겠지요. 정리해보면 A에서 D로 가는 최단 경로는 그것의 작은 문제인 A에서 C로 가는 최단 경로, 한번 더 작은 문제인 A에서 B로 가는 최단 경로의 결합을 통해 최종적인 A에서 D로 가는 최단 경로를 찾을 수 있습니다. 이렇게 다이내믹 프로그래밍을 적용하기 위해서는 작은 문제들의 최적 해법을 결합하여 최종 문제의 최적 해법을 구할 수 있어야 합니다.
지금까지 다이내믹 프로그래밍의 정의와 조건에 대해 살펴보았습니다. 그럼 이제부터 본격적으로 다이내믹 프로그래밍을 이용하여 피보나치 수열 문제를 다시 한번 해결해 봅시다.
Recursion + Memoization
도입부에서 다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용한다고 했던 것을 기억하시나요? Memoization 의 정의는 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술 입니다. 이제 재귀 함수에 과연 Memorization을 어떻게 적용할지 함께 확인해 봅시다.
function fibMemo(n, memo = []) {
if(memo[n] !== undefined) return memo[n];
// 이미 해결한 하위 문제인지 찾아본다
if(n <= 2) return 1;
let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
// 없다면 재귀로 결과값을 도출하여 res 에 할당
memo[n] = res;
// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
return res;
}먼저 fibMemo 함수의 파라미터로 n 과 더불어 빈 배열을 전달합니다. 이 빈 배열은 하위 문제의 결과값을 저장하는 데에 사용할 예정입니다.
memo 라는 빈 배열의 n 번째 인덱스가 undefined 가 아니라면, 즉 n 번째 인덱스에 어떤 값이 저장되어 있다면 저장되어 있는 값을 그대로 불러서 사용합니다.
undefined라면, 즉 처음 계산하는 수라면 fibMemo(n-1, memo) + fibMemo(n-2, memo)를 이용하여 값을 계산해 주고 그 결과값을 res 라는 변수에 할당해 줍니다.
마지막으로 res 를 리턴하기 전 memo 의 n 번째 인덱스에 res 값을 저장해 줍니다. 그 이유는 (n+1)번째의 값을 구하고 싶을 때 n번째 값을 memo 에서 꺼내 사용하기 위함입니다.
위의 과정을 이미지를 통해 다시 확인해 볼까요?
fib(7)을 구하기 위해서는 그저 앞서 저장해 놓은 하위 문제들의 결괏값을 가져다 사용하면 될 뿐이고, n이 커질수록 계산해야 할 과정은 선형으로 늘어나기 때문에 시간복잡도는 O(N) 이 됩니다. Memorization을 사용하지 않고 재귀 함수로만 문제를 풀 경우 n이 하나 커질수록 계산해야 할 과정이 두 배씩 늘어나 시간복잡도가 O(2^N)에 되는 것과 비교하였을 때, 다이내믹 프로그래밍의 강점을 확인할 수 있습니다.
더불어 fib(7)을 구하기 위해 fib(6)을 호출, fib(6)을 구하기 위해 fib(5)을 호출하는 풀이 과정이 마치 위에서 아래로 내려가는 것처럼 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 이 방식을 Top-down 방식이라 부르기도 합니다.
Iteration + Tabulation
앞서 재귀 함수를 이용하였다면, 이번에는 반복문을 이용하여 다이내믹 프로그래밍을 구현해 봅시다.
하위 문제의 결괏값을 배열에 저장해 놓고, 필요한 시 꺼내 사용하는 개념은 재귀 함수를 이용한 방법과 같습니다. 다만, 재귀 함수를 이용한 방법은 문제를 해결하기 위해 큰 문제부터 시작하여 작은 문제로 옮아가며 문제를 해결하였다면, 반복문을 이용한 방법은 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법입니다. 그 때문에 이를 Bottom-up 방식이라 부르기도 합니다.
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];
}
지금까지 피보나치 수열을 3가지 방법으로 구현해 보았습니다. 그럼 이제 다이내믹 프로그래밍이 시간복잡도를 얼마나 효과적으로 개선하였는지 눈으로 직접 확인해 보아야겠죠? 위 3가지 코드들을 크롬 개발자 도구에 복사한 뒤 동일한 수를 입력하였을 때 결괏값을 얻기까지 과연 얼마의 시간이 소요되는지 확인해 봅시다. (시간 측정 방법은 하단의 예시를 참고해 주세요) 특히 Top-down과 Bottom-up이 과연 동일한 소요 시간을 갖는지도 확인해 봅시다. 결과에 대한 원인 분석은 여러분이 직접 파악해 보시기 바랍니다.
질문
Top-down과 Bottom-up의 소요 시간을 비교하였을 때 결과는 어떠하였고, 그 원인은 무엇이었을까요?
다이내믹 프로그래밍과 탐욕 알고리즘은 각각 어떤 경우에 사용하기 적합한 알고리즘일까요?
크롬 개발자 도구에서 함수 실행 시간 측정 방법
함수 실행 시간 측정 방법에는 여러 가지가 있지만, 아래의 방법으로 간단하게 실행 시간을 확인해 볼 수 있습니다. 단, 실행 환경은 저마다 다르므로 아래 측정 방법은 이번 학습 용도로만 사용해 주세요.
var t0 = performance.now();
fib(50); // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')
