[자료구조/알고리즘]
Chapter - Dynamic Prograimng
Greedy Algorithm과 함께 언급하는 알고리즘이로 Dynamic Programing이 있다. DP라고 하는 이 알고리즘은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식이다.
Dynamic Programing의 원리는 주어진 문제를 여러 개의 하위 문제로 나누어 풀고 하위 문제들의 해결방법을 결합하여 최종 문제를 해결하는 문제 해결 방식이다. 하위 문제를 계산한 뒤 그 해결책을 저장하고 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 다시말해, 하나의 문제는 단 한번만 풀도록 하는 알고리즘이다.
- 큰 문제를 작은 문제로 나눌 수 있고 이 작은 문제가 중복해서 발견된다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.
첫 번째 조건인 “큰 문제를 작은 문제로 나눌 수 있고 이 작은 문제가 중복해서 발견된다.”는 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러번 반복해서 사용될 수 있어야 한다는 말과 같다. 이를 확인하기 위해 피보나치 수열을 예로 보면,
function fib(n) {
if(n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...피보나치 수열을 첫째와 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두항의 합과 같은 수열이다. 이 함수의 계산 과정을 그림으로 그려보면 다음과 같다.
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)
.....피보나치 수열은 위 예시처럼 동일한 계산을 반복적으로 수행해야 한다. 이과정에서는 fib(5)는 두번, fib(4)는 세번, fib(3)은 다섯번의 동일한 계산을 반복한다. 이렇게 작은 문제의 결과를 큰 문제를 해결하기 위해 여러번 반복하여 사용할 수 있을 때, 부분 문제의 반복이라는 조건을 만족한다.
두 번째 조건인 "작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다."를 보면 이 조건에서 말하는 정답은 최적의 해결방법을 의미한다. 따라서 두 번째 조건을 달리 표현하면 주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법을 찾아야 한다. 그리고 작은 문제들의 최적의 해법을 결합하면 결국 전체 문제의 최적 해법을 구할 수 있다.
최단 경로를 찾는 문제로 예를 들면,
A에서 D로 가는 최단 경로는 A → B → C → D이다. 그렇다면 A에서 C로 가는 최단 경로는 어떨까? A → B → E → C가 아닌 A → B → C순서일 것이다. 이렇게 다이내믹 프로그래밍을 적용하기 위해서는 작은 문제의 최적 해법을 결합하여 최종 문제의 최적 해법을 구할 수 있어야 한다.
Recursion + Memoization
다이나믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용한다. 이때 결과를 저장하는 방법을 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;
}- 먼저
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)이 된다. Memoization을 사용하지 않고 재귀함수로만 문제를 풀 경우 n이 커질수록 계산해야 할 과정이 두배씩 늘어나 시간 복잡도가 O()에 되는 것과 비교했을 때, 다이나믹 프로그래밍의 강점을 확인할 수 있다.
다이나믹 프로그래밍을 적용한 피보나치 수열에서 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];
}