동적 계획법 (다이나믹 프로그래밍, Dynamic programming)

동적 계획법 (동적 프로그래밍, 다이나믹 프로그래밍, Dynamic programming, DP 등)이란 

복잡한 하나의 문제를 작은 여러 개의 문제로 나누어 해결하는 방법을 의미합니다.

 

동적 계획법으로 풀기 위해서는 부분 반복 문제와 최적 부분 구조라는 두가지 조건을 만족해야 하는데 

각각의 정의는 다음과 같습니다.

 

1. 부분 반복 문제 (Overlapping Subproblem) 

 

피보나치 수열에서 102번째 항을 구하기 위해서 101번째항과 100번째 항을 구해야하고

101번째 항을 구하기 위해서는 100번째 항과 99번째 항이 필요하고.

100번째 항을 구하기 위해서는 99번째  항과 98번째 항이 필요합니다.

 

굵은 글씨로 된 부분이 연산의 중복이 발생하는 부분인데

첫번째 100번째 항은 102번째 항을 구하기 위한 요소로,

두번째 100번째 항은 101번째 항을 구하기 위한 요소로 사용되어 만약 별다른 처리 없이 프로그래밍을 하게 된다면

연산의 중복이 발생하게 됩니다.

 

이렇게 중복되는 연산을 부분 반복 문제(Overlapping Subproblem) 이라고 합니다.

이는 어느 한 문제가 여러 개의 작은 문제들로 나뉘어질 수 있을 때 사용하는 용어로 재귀 알고리즘을 이용하여

해결할 수 있습니다.

 

2. 최적 부분 구조 (Optimal Substructure)

 

최적 부분 구조란 작은 부분 문제에서 구한 최적의 답으로 큰 문제의 최적의 답을 구할 수 있어야 한다는 것을

의미합니다.

 

최적 부분 구조에서 문제의 크기와는 상관이 없이 어떤 한 문제의 답은 일정합니다.

즉, 어떠한 문제의 f(100)과 f(200)을 구하기 위해 사용하는 f(50)의 값은 항상 동일하다는 의미입니다.

 

 

위 두개의 조건을 합치면 동적 계획법으로 문제를 해결할 시 동일한 값을 여러 번 구한다 라는 결론을 얻을 수 있습니다.

이러한 문제를 해결하기 위해서 메모이제이션(Memoization)이라는 기법을 사용합니다.

 

메모이제이션

메모이제이션이란 메모리에 연산한 결과를 저장하여 반복연산을 수행할 경우 연산을 진행하지 않고 메모리에서 결과값을 가져오는 기법을 의미합니다. 

 

피보나치를 예시로 들면 100번째 항의 값 한번 구해놓았으면 이후 100번째 항이 필요할 때 연산을 반복할 필요 없이

메모리에서 불러오면 된다는 의미입니다.

 

---

동적 계획법을 이용하여 문제를 해결할 때 접근방법으로 2가지가 있습니다. 

첫 번째는 하향식 (Top-Down)

두 번째는 상향식 (Bottom-Up)

입니다.

 

하향식은 큰 문제를 작은 문제로 나누면서 재귀 호출을 이용하여 해결하는 방식이고

상향식은 작은 문제들을 풀어나가면서 큰 문제를 해결하는 방식으로 주로 반복문을 사용합니다.

 

 

동적 계획법을 적용하여 해결할 수 있는 문제의 예를 들면 피보나치 수열의 n번째 항을 구하는 방법이 있습니다.

피보나치 수열의 102번째 항을 구하기 위해서는 101번째 항과 100번째 항을 알아야합니다.

또 101번 째 항과 100번째 항을 알기 위해서는 추가적으로 99번째 항과 98번째 항을 알아야합니다.

이런 식으로 구해야할 항을 반복해서 구하다보면 우리가 구하려는 항의 일반적인 식을 알 수 있습니다.

피보나치의 경우는 n번째 항을 f(n) 이라고 할 때

---

f(n) = f(n-1) + f(n-2)

---

라는 것을 알 수 있습니다. 

일반식을 도출해 내었으니 이를 프로그래밍으로 구현하면 문제는 해결됩니다.

 

Top-Down

int mem[100]

mem[1] = 1;
mem[2] = 1;

int fib(int n)
{
  if (mem[n] != 0)//-1 등 다양하게 가능
      return mem[n];
  mem[n] = fib(n-1) + fib(n-2); // 재귀 호출
  return mem[n];
}

 

Bottom-Up

int mem[100];

mem[1] = 1;
mem[2] = 1;

int fib(int n)
{
  for(int i = 3; i <= n; i++)
  {
  	mem[i] = mem[i-1] + mem[i-2];
  }
  return mem[n];
}

 

동적 계획법을 통하여 피보나치를 해결하는 방법을 알아보았습니다.

동적 계획법과 함께 같이 거론 되는 알고리즘 중 하나는 탐욕 알고리즘 (그리디 알고리즘)이 있는데

 

동적 계획법은 모든 경우를 다 살펴보기 때문에 속도가 느리지만 늘 최적의 해를 구할 수 있다는 특징이 있고

탐욕 알고리즘은 작은 문제들 중 해당 순간의 최적의 해를 구하기 때문에 전체 문제의 최적의 해가 아닐 수 있지만

빠르다는 특징이 있습니다.

 

 

참고 자료

https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

동적 계획법(Dynamic Programming)

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

메모이제이션 - 위키백과, 우리 모두의 백과사전

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