DP; 동적 계획법

Ramne·2021년 8월 24일

알고리즘

Dynamic Programming

"하나의 문제는 단 한 번만 풀도록 하는 알고리즘"

DP vs Divide & Conquer

주어진 문제를 작은 부분 문제들로 나누고 해를 모아 해결하는 기본 개념은 동일하다.
모두 재귀를 이용하여 구현한다.

DP vs Greedy

작은 문제에서부터 출발한다는 점은 같으나
그리디는 매 순간 최적의 선택을 찾는 방식이고
DP는 모든 경우의 수를 조합해 최적의 해를 찾는 방식이다.

동적 계획법의 원리

문제를 여러 개의 하위 문제로 나누어 풀고, 해결 방법을 결합하여 최종 문제를 해결한다.

하위 문제를 계산한 뒤 그 해결책을 저장하고,
나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.

동적 계획법을 사용할 수 있는 조건

큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

⚠️ 주의 할 점
주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라,
작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 한다.

이 과정에서 "메모이제이션"이 사용된다는 점에서 분할 정복과 차이가 있다.
이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산이 필요할 시
저장한 값을 단순히 반환하기만 하면 된다.

일반적으로 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다.
(다만 '정렬'과 같은 몇몇 요소는 예외로 퀵 정렬이나 병합 정렬은 매우 빠르다.)
단순 분할 정복으로 풀면 심각한 비효율을 낳는 대표적 예시로 피보나치 수열이 있다.

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;
} 
// 다이나믹 프로그래밍을 적용한 피보나치 수열

코드 해설

2번째 파라미터로 전달한 빈 배열은 하위 문제의 결과값을 저장하는 데에 쓰인다.

n 번째 인덱스에 값이 저장되어 있다면, 저장되어 있는 값을 사용하고
처음 계산하는 수라면 재귀를 통해 값을 계산한 후 그 결과값을 변수에 할당한다.

마지막으로 변수를 리턴하기 전에 memo 의 n 번째 인덱스에 값을 저장하면
(n+1)번째의 값을 구하고 싶을 때, n번째 값을 memo에서 찾아 재사용할 수 있다.

이렇게 저장한 하위 문제의 결과값을 사용하면
n이 커질수록 계산해야 할 과정은 선형으로 늘어나기 때문에 시간 복잡도는 O(N) 이다.

Memorization없이 재귀 함수로만 풀 경우,
n이 커질수록 계산 과정이 두 배씩 늘어나 시간 복잡도가 O(2^N)에 되는 것과 비교하면, 다이내믹 프로그래밍의 강점을 확인할 수 있다.

다이내믹 프로그래밍을 적용한 피보나치 수열을 보면 풀이 과정이 위에서 아래로 내려간다.
큰 문제를 해결하기 위해 작은 문제를 호출하는 이 방식을 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];
}