Dynamic Programming

Dynamic Programming

동적계획법이란: 큰 문제를 작은 문제로 나누어 푸는 방법

언제 쓰는가?

• 부분 문제 반복 및 최적 부분 구조를 가지고 있는 알고리즘에 사용
• 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용

왜 쓰는가?

• 알고리즘을 일반적인 방법에 비해 더 적은 시간 내에 풀기 위함이다.
• 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토, 그 중 최적의 풀이법을 찾아냄에 있어 효율적

어떻게 쓰는가?

• 일반적으로 주어진 문제를 풀기 위해, 문제를 여러 하위 문제로 나누어 푼다.
• 여러 하위 문제를 푼 후, 그 해결책을 저장한다.
• 이 후 같은 하위 문제가 나왔을 경우 이전의 해결책으로 정리한다.

예를 들어 피보나치 수열을 보자.
일반적인 피보나치 수열의 알고리즘은 다음과 같다.

function fib(n)
 if n = 0
  return 0
 else if n=1
  return 1
 else
  return fib(n-1) + fib(n-2)

이와 같이 해결할 경우 다음의 이미지처럼 함수들을 호출하게 된다.

fib(1)과 fib(0) 등 이미 한번 불렀던 함수를 각각 2번 이상을 호출하게 된다.
이미 진행했던 연산인데도 중복적으로 연산을 수행하는 것은 매우 비효율적이다.

동적 계획법은 이를 방지한다.
처음 진행되는 연산은 기록해두고 이후 이전에 진행한 연산의 결과가 필요할 경우 그대로 꺼내오는 작업을 진행한다.

동적 계획법에 의하면 피보나치 수열은 다음과 같이 새로 짤 수 있다.

int fiboData[100] = {0,};

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

이렇게 하면 이전에 계산했던 데이터들은 이미 저장되어 있고, 해당 데이터만 불러오기 때문에 중복되는 연산을 수행하지 않는다.

---

구현 방법

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];
}

이 피보나치 함수를 보자.
0이라는 단계부터 1 단계, 2 단계, 차근 차근히 수행해 나간다.
가장 아래서부터 진행해 나가는 방법이다.

Top-down

큰 문제서부터 작은 문제로까지 진행을 한다.

• 그러다보니 재귀함수로 구현되는 경우가 대부분이다.
• 큰 문제가 바로 풀리지 않아 점점 작아지는 문제로 진행해야 하기 때문이다.

int fiboData[100] = {0,};

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

동적 계획법 vs 그리디 알고리즘

• 동적 계획법
  • 모든 방법을 일일이 검토하여 최적의 해를 찾아낸다.
  • 그리디 알고리즘에 비해 시간이 오래걸림
  • 결과적으로는 항상 최적의 해를 구하게 된다.
• 그리디 알고리즘
  • 모든 해를 구하지 않고 그 순간의 최적의 해를 찾는다.
  • 운이 좋다면 훨씬 빠른 속도로 최적의 해를 찾을 순 있지만,
  • 항상 최적의 해라고는 보기 어렵다.