동적 계획법

주요 키워드

dp, memoization(메모이제이션) , 반복/재귀

 

<dp를 사용하는 이유>

 

→ 반복되는 계산을 막기 위해서.

가장 대표적인 예 → 피보나치 수열

 

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

이러한 식으로 겹치는 계산이 발생한다면 이를 그때그때 다 계산하지않고 한 번 계산한 값을 계속 사용!

피보나치 수열

 

피보나치 수열은 제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

프로그래밍에서 피보나치 수열은 보통 재귀를 통해 표현

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

fibo(6)은 어떻게 실행될까?

 

fibo(4)

의 연산이 두 번,

fibo(3)

의 연산이 세 번 진행되는 것을 볼 수 있다. 이미 진행됐던 연산인데도 불구하고!!!

 

위의 예시처럼 이미 했던 연산이 반복되는 결점을 보완하기 위해서 동적 계획법(Dynamic Programing, DP)

처음 진행되는 연산은 기록해 두고, 이미 진행했던 연산이라면 다시 연산하는 것이 아니라 기록되어 있는 값을 가져온다

 

<동적 계획법으로 구하는 피보나치 수열>

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

fiboData라는 배열을 생성

이 배열에는 연산한 값들이 저장

 

n이 2 이하일 경우 1을 반환하고, 그 이상일 경우 fiboData[n]에 연산 값이 없는지 검사한다

없을 경우, 새로 연산해서 fiboData[n]에 값을 저장하고, 반환한다. 만약 연산 값이 존재한다면 바로 fiboData[n]을 반환하게 된다. 재귀와는 다르게 중복되는 연산이 사라진것을 알 수 있다.

 

<동적 계획법의 개념>

 

동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘!!!

메모이제이션(Memoization)

 

위의 코드에서는 하위 문제를 해결할 때 그 해결책을 저장해 두고, 똑같은 문제가 발생했을 때 저장되어 있던 해결책을 가지고 간단하게 해결했다. 이렇게 동일한 문제를 반복해야 할 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것을 메모이제이션(Memoization)

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

 

TOP-DOWN 방식과 다르게 문제 풀이가 아래에서 위로 진행되는 것

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 방식입니다.

 

<장점과 단점>

 

동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘

그리디 알고리즘은 모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 찾는 방식

 

그리디 알고리즘은 닥치는 순간만을 고려해서 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 수는 없다!! 하지만 동적 계획법은 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택한다. 그런 면에서 동적 계획법은 그리디 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가지고 있다.

 

Memorization의 경우,  재귀를 이용하기 때문에 값을 위에서부터 계산하여 필요없는 계산은 안 해도 된다!

하지만 스택이 너무 많이 쌓여서 과부화가 걸려 문제가 생길 수도 있다.

 

반면에, Tabulation은 그럴 위험은 없지만 표를 하나씩 밑에서부터 채워야 하기때문에

필요 없는 값을 계산 해야 할 수도 있다.