📖 '누구나 자료구조와 알고리즘' 책을 공부한 내용을 담고 있습니다.
12장 동적 프로그래밍
12장에서 재귀 코드의 속도를 느리게 만드는 원인을 찾고, 빅 오 관점에서 어떻게 나타내는지 배워보자.
12.1 불필요한 재귀 호출
다음 예제는 배열에서 최댓값을 찾는 문제이다. 재귀 함수를 활용해서 배열의 최댓값을 구현해 보았다.
function max(array) {
// 기저조건: 원소가 하나면 그 원소가 최댓값
if (array.length === 1) return array[0];
/** 첫 번째 원소와 나머지 배열에서 가장 큰 원소를 비교한다.
첫 번째 원소가 더 크면 그 원소를 최댓값으로 반환한다.
그렇지 않으면 나머지 배열의 최댓값을 반환한다.
*/
if (array[0] > max(array.slice(1, array.length - 1))) {
return array[0];
// 그렇지 않으면 나머지 배열의 최댓값을 반환한다.
} else {
return max(array.slice(1, array.length - 1)))
}
}예를 들어, 배열 [1,2,3,4]에서 최댓값을 찾는다면, 첫 번째 원소인 1과 배열 [2,3,4]의 최댓값을 비교한다. 이어서 2와 [3,4]의 최댓값을 비교하고, 3과 [4]를 비교한다. [4]로 한번 더 재귀 호출을 수행하는데 이때 기저조건에 해당한다.
max 재귀 분석
max([4])부터 호출 사슬 위로 올라가면 max([4])는 기저 조건에 해당하므로 4를 반환한다.
if (array.length === 1) return array[0];max([3,4])는 max([4])를 2번 호출한다. 이렇게 모든 재귀 함수를 호출해보면 불필요한 호출이 발생한다. max([4])는 한 번만 계산해도 충분한데, 예제에서는 8번이나 호출한다.
12.2 빅 오를 위한 작은 개선
다행히도 불필요한 재귀 호출을 없애는 손쉬운 방법이 있다. 코드에서 max를 딱 한 번만 호출하고 그 결과를 변수에 저장하면 된다.
function max(array) {
// 기저조건: 원소가 하나면 그 원소가 최댓값
if (array.length === 1) return array[0];
let max_of_remainder = max(array.slice(1, array.length - 1))
if (array[0] > max_of_remainder) {
return array[0];
// 그렇지 않으면 나머지 배열의 최댓값을 반환한다.
} else {
return max(array.slice(1, array.length - 1)))
}
}이렇게 간단한 수정으로 max함수를 4번만 호출한다.
12.3 재귀의 효율성
위 개선된 max 함수는 배열 내 원소 개수만큼 자신을 재귀적으로 호출한다. 이 함수의 빅 오는 O(N)이다.
하지만 개선되기 전 max 함수 호출 횟수를 보면, 원소 개수가 1개씩 커질 때, 호출 횟수는 약 2배씩 늘어난다. O(2^N)이다. 현저히 느린 알고리즘이다.
| 원소 개수(N) | 호출 횟수 |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
두 함수의 효율성 차이는 매우 크다. 불필요한 재귀 호출을 피하는 것이 재귀 효율성을 높이는 데 핵심이다.
12.4 하위 문제 중첩
피보나치 수열(Fibonacci sequence)
0과 1로 시작하며 이어지는 수는 수열의 앞 두 수의 합이다.0,1,1,2,3,5,8,13,21,34,55
예를 들어, 피보나치 수열의 N번째 수를 반환하는 함수가 있다. 함수에 10을 전달하면 수열의 10번째 수가 55이므로 55를 반환한다. (0은 수열에서 0번째 수로 간주된다.)
function fib(n) {
// 기저 조건은 수열의 처음 두 수다.
if (n === 0 or n === 1) return n;
// 앞의 두 피보나치 수의 합을 반환한다.
return fib(n-2) + fib(n-1)
}이 함수 또한 자기 자신을 두 번씩 호출하는 문제가 있다. 시간 복잡도는 O(2^N)이다. 하지만, 피보나치 수열은 이전 예제처럼 쉽게 최적화가 쉽지 않다.
변수에 저장할 데이터가 하나가 아니기 때문이다. fib(n-2)와 fib(n-1) 모두 계산해야 한다. 이를 컴퓨터 과학에서 하위 문제 중첩(overlapping subproblems)이라 부른다.
하위 문제 중첩이 발생하는 이유는 fib(n-2)와 fib(n-1)이 결과적으로 같은 함수를 여러 번 중복 호출하기 때문이다.
12.5 메모이제이션을 통한 동적 프로그래밍
동적 프로그래밍을 통해 피보나치 수열의 하위 문제 중첩을 해결할 수 있다.
동적 프로그래밍(dynamic programming)을 통한 알고리즘 최적화 기법을 알아보자
알고리즘 최적화 기법: 메모이제이션(memoization)
메모이제이션은 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다.
해시 테이블에 함수 결과를 저장해서 중복 호출을 막는다.
피보나치 예제에서 fib(3),fib(4),fib(5),fib(6) 호출했을 때 해시테이블
{
3: 2,
4: 3,
5: 5,
6: 8
}그렇다면, 재귀함수에서 해시 테이블에 어떻게 접근할까?
피보나치 함수의 두 번째 인자로 해시 테이블을 전달하면 된다.
메모이제이션 구현
함수 처음 호출할 때 빈 해시 테이블을 두 번째 인자로 전달한다.
function fib(n, memo) {
// 기저 조건은 수열의 처음 두 수다.
if (n === 0 or n === 1) return n;
// 해시 테이블 memo에 fib(n)의 값이 있는지 확인
if (!memo[n]) {
/** n이 memo에 없으면 fib(b)을 계산 후
결과값을 해시 테이블에 저장한다.
*/
memo[n] = fib(n-2,memo) + fib(n-1,memo)
}
/** 이제 fib(n)의 값이 memo에 저장돼 있다.
따라서, 그 값을 반환한다.
*/
return memo[n]
}참고로, memo에 기본값을 할당하면 빈 해시 테이블을 명시적으로 전달하지 않아도 된다.
function fib(n, memo={}) {
// 코드 생략
}그렇다면, 메모이제이션 사용한 함수의 빅 오는 무엇일까?
N에 대해서 2N - 1 호출된다. 빅 오에서는 상수를 버리기 때문에 O(N)이 된다. O(2^N)에 비해 효율성이 크게 개선되었다.
| 원소 개수(N) | 호출 횟수 |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 5 |
| 4 | 7 |
| 5 | 9 |
| 6 | 11 |
12.6 상향식을 통한 동적 프로그래밍
"상향식"으로 하위 문제 중첩을 해결해 보자
상향식은 재귀 대신 루프 같은 다른 방식으로 해결한다는 뜻이다.
12.6.1 상향식 피보나치
상향식에서는 0, 1로 시작한다. 루프를 사용해서 수열을 만든다.
function fib(n) {
if (n === 0) return 0;
// a와 b는 각각 수열의 처음 두 수로 시작한다.
let a = 0;
let b = 1
for (let i = 1; i < n; i++) {
/**a와 b가 다음 수가 된다.
a는 b가 되고, b는 이전 a + 이전 b
이전 a는 temp로 저장해서 계산한다.
*/
let temp = a;
a = b
b = temp + a
return b;
}
}N까지의 간단한 루프로 N단계가 걸리므로 O(N) 시간 복잡도이다.
메모이제이션 대 상향식
메모이제이션을 쓰더라도 재귀가 반복에 비해 오버페드가 더 든다. 재귀를 어떻게 사용하든 호출 스택에 호출을 기록해야 하므로 메모리를 소모한다. 메모이제이션도 해시테이블을 사용해서 메모리를 추가로 소모한다.
재귀가 매우 직관적이지 않는 이상 일반적으로 상향식을 택하는 편이 더 낫다. 재귀가 더 직관적이면 재귀를 사용하되 메모이제이션을 사용하자.
요약
- 재귀 함수가 같은 계산을 반복하여 수행함으로써 불필요한 재귀 호출 발생
- 불필요한 재귀 호출을 변수에 결과 저장으로 최소화
- 하위 문제 중첩: 피보나치 수열과 같은 일부 문제는 같은 하위 문제를 반복해재귀 함수의 효율성을 크게 저하
- 메모이제이션은 해시테이블에 계산된 결과를 저장하여 효율을 높임.
- 상향식 접근은 재귀 대신 반복문을 사용
- 메모이제이션은 메모리 추가 사용이 필요, 상향식이 메모리 측면에서 유리
