[알고리즘] Dynamic Programming ( 동적 계획법 )

• dynamic programming에 대한 개념 설명
• dynamic programming을 적용하기 위한 조건 
• dynamic programming의 특징
• dynamic programming의 접근법

---

Dynamic Programming은 보통 DP라고 줄여 쓰는것을 볼 수 있다.

이름만 봤을때는 뭔가 엄청나게 대단하고 복잡한 알고리즘일것 같은데, 실제 해당 내역을 공부하면 이름이랑 뭔가 맞지 않는다는게 느껴진다.

 

보통 인터넷을 찾아봤을때, Dynamic Programming의 정의는 아래와 같다.

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 

개념은 그렇게 어렵지 않고, 받아들일수 있다.

그러면, 이러한 DP를 어떠한 상황에 적용할 수 있는지 알아보자.

가장 대표적인 예시로는 피보나치 수열이 있다. 

 

간단하게 피보나치 수열에 대한 정의를 보면 아래와 같다.

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 이다.
처음 여섯 항은 각각 (0), 1, 1, 2, 3, 5, 8이다.
편의상 0번째 항을 0으로 두기도 한다.

DP라는 개념이 등장하기 전에는 대부분 해당 문제를 재귀적으로 해결하였다. 

아래는 예시 코드이다.

int fibonacci(int n) {
    if (n<=2)
      return 1;
    else
      return fibonacci(n-1) + fibonacci(n-2);
}

 

하지만 해당 방법으로 문제를 풀게 된다면, 반복되는 값들을 반복적으로 구한다는 문제가 있다. 

아래의 그림에서 트리에서 반복적으로 fib(5) 이하의 노드들을 계산하게 된다. 

한번만 계산해 놓고 해당 값을 다시 만나면 이전에 계산해 놓은 값을 가져다가 쓰기만 하면 계산 시간을 효율적으로 줄일 수 있게된다.

이러한 점을 반영하여서 DP의 적용 조건과 특징을 살펴보자.

---

DP의 적용 조건

• 부분문제 반복 ( Overlapping Subproblem )
  • 피보나치 수열과 같이  f(n) = f(n-1) + f(n-2) 와 같이 
    어떠한 문제가 여러개의 부분 문제로 쪼개 질 수 있고, 해당 부분 문제가 또 다시  재귀적으로 부분 문제로 쪼개질 수 있는 것
• 최적 부분구조 ( Optimal Substructure )
  • 피보나치 수열과 같이 f(n) = f(n-1) + f(n-2)와 같이
    작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있는 것

( 해당 조건은 뭔가 전문적인 단어들이 들어가서 어렵게 표현된 것처럼 보이는데, DP의 핵심은 "복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 것" 이다. 이 핵심을 풀어서 전문적으로 설명해 놓은게 조건이라고 생각하자.)

---

DP의 특징으로는 Memorization이다.

반복적으로 등장하는 계산을 기억해 두었다가, 해당 계산이 다시 등장할때, 재계산을 하지 않고 기억해 두었던 값을 가져다 사용하는 것이다. 

위의 피보나치 수열 그래프에서 반복적으로 등장하는 fibo(5), fibo(4) ... 값들을 기억하고 사용하면 된다. 

---

접근법

이제 개념적인 부분과 특징을 알아 보았으니 실제로 문제를 만났을때 어떻게 접근해야하는지에 대해서 알아보도록 하자.

크게 2가지 방법이 있다. 

• Top-Down
  • 재귀로 해결 하는 대부분의 방식
  • 큰 문제를 해결 하기 위해 작은 문제로 나누고, 해당 값이 아직 계산되지 않은 경우 더 작은 값으로 나누며 값을 찾아가는 방식
  • ( 예시는 위의 fibonacci 코드 )
• Botton-up
  • 작은 문제에서 부터 하나씩, 하나씩 값을 찾아가는 방식
  • ( 예시는 아리의 코드 )

int fibonacci (int n) {
  fibodata[0] = 0;
  fiboData[1] = 1;
  for (int i=2; i<=n; i++) {
    fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
  }
  return fiboData[n];
}