내용에 앞서

학교에서 컴퓨터 공학 이론 스터디를 진행하고 있습니다. 매주 발표하는 내용을 시리즈로 업로드할 예정입니다. 공부 목적으로 작성되는 글이니 부족한 부분, 참고하면 좋을 내용 등 여러 피드백은 댓글로 주시면 감사히 읽도록 하겠습니다!

배경

피보나치 수열

동적 계획법의 등장 배경은 피보나치 수열을 통해 알 수 있습니다. 피보나치 수열은 제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의됩니다. 제0항은 생략하기도 합니다. 수열은 아래와 같습니다.

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

프로그래밍에서 피보나치 수열은 보통 재귀를 통해 표현합니다. 아래는 피보나치 수열의 n번째 수를 구하는 함수입니다.

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

fibo(6)을 호출하게 되면 어떤 흐름으로 전개될까요? for문 내에서 fiboData[2]부터 fiboData[6]까지 점진적으로 계산해 나가겠죠. 이렇게 처음 값부터 계산해 최종 값까지 계산해 내는 것이 BOTTOM-UP 방식입니다.

장점과 단점

동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘입니다. 여기서 그리디 알고리즘(탐욕 알고리즘)과 대비됩니다. 그리디 알고리즘은 모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 찾는 방식입니다. 그리디 알고리즘은 닥치는 순간만을 고려해서 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 수는 없겠죠. 하지만 동적 계획법은 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택합니다. 그런 면에서 동적 계획법은 그리디 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가지고 있습니다.

스터디 발표 자료

https://www.slideshare.net/ssuser889640/dynamic-programming-232156153