Dynamic Programming - 동적 계획법

출처 : https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

 

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

 

문제를 풀기 위해, 문제를 여러 개의 하위 문제 (subproblem)으로 나누어 푼 다음, 그것을 결합하여 최종 목적에 도달하는 것

 

하위 문제의 해결방법을 찾았는데 같은 하위 문제가 계속해서 나올 경우 계산 횟수를 줄일 수 있다.

 

 

---

출처 : https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182

 

이름은 다이내믹 프로그래밍이지만 전혀 다이나믹하지도 않고 프로그래밍이라기보다는 테이블을 만드는 기법입니다.

 

대표적인 동적 프로그래밍으로 메모이제이션이 있습니다.

 

메모이제이션이란, 재귀 호출 시에 반복적인 계산을 막기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법을 말합니다.

 

---

 

1. 막대기 자르기

 

하나의 긴 막대기가 있는데 막대기 조각마다 가격이 다릅니다. 막대기를 적절하게 잘라서 가장 가격이 높게 만들어야 합니다.

 

길이(i) 0 1 2 3 4 5 6 7 8 9 10

가격(Pi) 0 1 5 8 9 10 17 17 20 24 30

 

예로 길이가 4인 막대기를 자를 때 얻을 수 있는 최대 가격은, 길이를 2인 막대기 두 개로 나누어서 가격을 5 + 5 = 10으로 만드는 겁니다. 길이가 6인 막대기는 자르지 않고 그냥 팔았을 때 최대 17의 가격을 얻을 수 있습니다. 

 

이 문제에 동적 프로그래밍을 적용하면 간단히 풀 수 있습니다.

 

길이가 n인 막대기의 최대 가격을 Rn이라고 했을 때, Rn = max(Pi + Rn - 1) (i는 1부터 n)로 나타낼 수 있습니다. max는 여러 값 중의 최댓값을 의미합니다. 예를 들면 아까 길이가 4인 막대기의 최대 가격은 R4 = max(P1 + R3, P2 + R2, P3 + R1, P4 + R0)이죠.

 

P1 , P2, P3는 이미 주어져 있으므로 R1, R2, R3를 구해야 하는데요, R1 = max(Pi + Rn-i)(i는 1부터 n)식에서 max(Pi + R0)이므로 1입니다.

 

R2는 max(P1 + R1, P2 + R0)이라 max(2, 5) = 5입니다. R3는 max(P1 + R2, P2 + R1, P3 + R0)라서 max(6, 6, 8) =8입니다.

R4는 위의 값들로부터 max(9, 10, 9, 9) = 10 임을 알 수 있습니다.

 

위의 과정에서 R1, R2, R3는 계속해서 나옵니다. 이 값들을 저장해 두고 재사용하면 일일이 재계산하지 않아도 되죠. 바로 여기서 Top-down으로 불리는 메모이제이션을 사용할 수도 있고, Bottom-up이라 불리는 상향식 계산법을 사용할 수도 있습니다.

 

 

---

피보나치 수열 예시

 

Top-Down

 

int fiboData[100]={0,};
 
int fibo(int n)
{
    if (n <= 2)
        return 1;
 
    if (fiboData[n] == 0 )
        fiboData[n] = fibo(n-1) + fibo(n-2);
 
    return fiboData[n];
}
 
 

 

fibo(6)을 호출하게 되면 fibo(6)부터 작은 수를 호출하여 가장 작은 수 까지 도달하게 되는 방식입니다.

 

 

 

Bottom-up

 

int fibo(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];
}

 

for문 내에서 fiboData [2]부터 fiboData [6]까지 점진적으로 계산해 나가며 최종 값까지 계산해 내는 것이 Bottom-up 방식입니다.