동적 계획법은 큰 문제를 작은 문제로 나눠서 최종 문제를 해결하는 알고리즘이다.
작은 문제를 처리할 때 수행되는 답을 저장해 놓고 다음번에 필요할 때 그 값을 불러와서 처리한다. 재활용 개념이라고 이해하면 쉽다. 분할 정복과 비슷한 개념이지만 분할 정복과 동적 계획법의 차이점은 분할 정복에서의 쪼개진 작은 문제들은 중복되지 않지만 동적 계획법에서 쪼개진 문제는 서로 연관성이 있다는 점이다.
(분할 정복에 대해서는 나중에 공부한 후 포스팅 예정입니다.)
개념
동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고, 그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘입니다. 피보나치 수열을 재귀로 표현했을 때 결함이 생기는데 이를 동적 계획법으로 보완한 사례를 보면서 알아 보겠습니다.
동적 계획법의 배경
동적 계획법의 등장 배경은 피보나치 수열을 통해 알 수 있습니다. 피보나치 수열은 제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 방식 (재귀) : 분할 정복, 큰 문제를 작은 문제들로 풀어나가는 방법.
- 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
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 방식입니다.
장점과 단점
동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘입니다. 여기서 그리디 알고리즘(탐욕 알고리즘)과 대비됩니다. 그리디 알고리즘은 모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 찾는 방식입니다. 그리디 알고리즘은 닥치는 순간만을 고려해서 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 수는 없습니다. 하지만 동적 계획법은 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택합니다. 그런 면에서 동적 계획법은 그리디 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가지고 있습니다.
출처: velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP/ yeoeun-ji.tistory.com/41
