[자료구조 & 알고리즘] 9. 동적 계획법

동적 계획법

1. 동적 계획법 (DP, Dynamic Programming)

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 해결한 뒤, 그 결과를 저장하고 다시 사용함으로써 중복 계산을 피하여 문제의 해를 효율적으로 찾아내는 방법.

• 중복 하위 문제와 최적 부분 구조를 가지고 있는 문제에 사용함.

     - 중복 하위 문제 (Overlapping Subproblem) : 어떤 하나의 문제가 여러 개의 하위 문제(또는 부분 문제, Subproblem)로 쪼개져 그것이 반복되는 구조.

     - 최적 부분 구조 (Optimal Substructure) : 부분 문제에서 구한 최적의 답을 합쳐 큰 문제의 최적의 답을 구할 수 있는 구조.

• 문제에 대한 정답이 될 가능성이 있는 모든 해결책을 고려해야 함.

     - 문제에 대한 정답이 될 가능성이 있는 모든 방법을 탐색하는 풀이법 = 완전 탐색

     - 하지만 중복 계산을 하지 않아 효율적으로 문제를 해결하는 것이 완전 탐색과 큰 차이점.

 

2. 동적 계획법 구현

• 구현 방법

     1. 크고 복잡한 문제를 작은 문제로 나눈다.

     2. 하위 문제의 답을 계산한다.

          - 중복 계산해야 하는 하위 문제가 있다면 한 번 계산한 결과는 메모리에 저장하여 재계산 하지 않도록 한다.

          - 이를 Memoization이라고 한다.

     3. 하위 문제에 대핸 답을 통해 원래 문제에 대한 답을 계산한다.

• 예시

     - 피보나치 수열

          - 일반적인 재귀를 이용하여 피보나치 수열을 풀면 중복 계산이 매우 많이 일어남.

     - f(6) 1번, f(5) 2번, f(4) 3번, f(3) 5번, f(2) 8번, f(1) 5번의 계산이 일어남.

     - DP를 사용할 경우 각 계산 값을 메모리에 저장해두고, 다음에 다시 해당 계산이 필요할 때 저장해놓은 값을 꺼내어 사용하여 중복 계산을 방지.

 

• Top-down 방식 (Memorization)

     - 구해야 하는 f(n)을 바로 호출하여 재귀를 통해 f(0)까지 내려오는 방식.

     - 재귀를 사용하여 구현 시간이 빠름.

private static int topDown(int n) {
    if(n <= 2) return topDownMemo[n] = 1;
    if(topDownMemo[n] == -1) topDownMemo[n] = topDown(n-1) + topDown(n-2);
    return topDownMemo[n];
}

 

• Bottom-Up 방식 (Tabulation)

     - f(0)부터 시작하여 반복문을 통해 f(n)까지 올라오는 방식.

     - 반복문을 사용하여 실행 시간이 빠름.

private static int bottomUp(int n) {
    bottomUpMemo[2] = bottomUpMemo[1] = 1;
    for(int i = 3; i <= n; i++) {
        bottomUpMemo[i] = bottomUpMemo[i-1] + bottomUpMemo[i-2];
    }
    return bottomUpMemo[n];
}

 

• 완전 탐색으로 풀다가 재귀나 반복문 등이 필요할 경우, 중복적인 답이 나오는지 체크해보고 나온다면 DP를 고려해볼 수 있음.

• Optimum value (최대, 최소 값), 방법의 개수 등을 구할 때 자주 쓰임.

     - ~의 최소 비용, ~의 최대 이익, ~를 하는 방법의 개수, 가장 긴~ ...

• 미래의 계산이 앞선 계산 결과에 영향을 받을 때

     - 단순한 분할 풀이 방식은 앞선 계산 결과가 뒤에 계산에 영향을 주지 않음.