5-1. 다이나믹 프로그래밍

다이나믹 프로그래밍

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘을 말한다. Devide and Conquere와 비슷하지만, 큰 문제를 작은 문제로 나눴을 때 작은 문제들 중 동일한 문제를 계산하지 않는다는 차이점이 있다.
• 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.
  • 겹치는 부분 문제가 나타난다. (Overlapping Subproblem)
  • 최적 부분 구조가 나타난다. (Optimal Substructure) 즉, 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
• 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 따라서, 정답을 한 번 구했으면 정답을 어딘가에 저장해놓는다. 이런 방법을 Memoization이라고 한다.
• 다이나믹 프로그래밍을 해결하는 방법에는 Top-down과 Bottom-up이 있다.
  • Top-down은 큰 문제에서 점차 작은 문제를 해결하는 방식으로, 재귀를 사용하게 된다.
    • 문제를 작은 문제로 나눈다.
    • 작은 문제를 해결한다.
    • 작은 문제의 결과를 통해 문제를 해결한다.
  • Bottom-up은 작은 문제에서 점차 큰 문제를 해결하는 방식으로, 반복문을 사용하게 된다.
    • 문제를 크기가 작은 문제부터 차례대로 해결한다.
    • 문제의 크기를 점차 확장시키면서 문제를 해결한다.
    • 작은 문제들을 해결했기 때문에, 큰 문제는 항상 해결할 수 있다.
    • 반복해서 진행하다보면 문제가 해결되는 시점을 알 수 있다.
  • Top-down과 Bottom-up의 시간 복잡도는 크게 차이가 나지 않는다. 다만 고차원적인 문제의 경우에는 Top-down방식으로만 해결할 수 있거나, Bottom-up방식으로만 해결할 수 있는 경우도 있다.

 

피보나치 수열로 알아보는 Overlapping Subproblem

• 피보나치 수열은 아래와 같은 조건을 만족한다.

  • F0=0
  • F1=1
  • Fn = F(n-1)+F(n-2) (단, n>=2)

• 크기 n이 존재하며, 큰 문제F(n)이 작은 문제(F(n-1), F(n-2))로 나뉘어진다.\

  • N번째 피보나치 수를 구하는 문제는 N-1번째 피보나치 수를 구하는 문제와 N-2번째 피보나치 수를 구하는 문제로 나뉘어진다.
  • N-1번째 피보나치 수를 구하는 문제는 N-2번째 피보나치 수를 구하는 문제와 N-3번째 피보나치 수를 구하는 문제로 나뉘어진다.
  • 위의 작은 문제들 중 겹치는 문제 N-2번째 피보나치 수를 구하는 문제는 계산의 결과가 달라지지 않는다. 즉, 작은 문제의 정답으로부터 문제의 정답을 구할 수 있다.(Optimal Substructure) 따라서 계산 결과를 저장해놓음으로써 겹치는 문제는 단 한번만 풀 수 있다.

• Memoization을 이용하여 피보나치 수를 구하는 코드는 아래와 같이 작성할 수 있다.

    int memo[100];
    int fibonacci(int n) {
        if(n<=1) {
            return n;
        } else {
              if(memo[n]>0) {    //memo[n]의 값이 0보다 큰 경우, 정답을 한 번 구했던 문제를 의미한다.
                return memo[n];
            }
            memo[n] = fibonacci[n-1]+fibonacci[n-2];
            return memo[n];
        }
    }

  다이나믹 프로그래밍에서는 모든 문제를 한 번씩만 풀기 때문에, 시간복잡도는 O(n)이 된다.