인트로
+컴퓨터공학을 전공하셨거나 코딩 테스트를 준비하시는 분들은 한 번쯤 접해보셨을 동적 프로그램(DP, 동적 계획법)을 쉽게 이해하기 위해 작성한 글입니다.
★
동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법이다. 이렇게 보면 동적 프로그래밍은 분할 정복이 동일하다고 생각할 수 있지만 해를 구하기 위해 쪼갠 "부분 문제"의 특성이 다르다. 분할 정복과 비교했을 때 동적 프로그래밍의 도드라지는 특성은 작게 쪼개진 "부분 문제"가 중복돼서 나타난다는 것이다.
이에 대해선 차차 알아보기로 하고 알기 쉽게 동적 프로그래밍을 이해해 보자.
동적 프로그래밍 (DP, 동적 계획법)
피보나치 수열을 예로 들어 동적 프로그래밍을 설명하려 한다.
다음은 피보나치 수열의 점화식이다.
코드에 가깝게 표현하면 다음과 같다.
F[1] = 1;
F[2] = 1;
F[i] = F[i - 1] + F[i - 2];
점화식으로부터 알 수 있는 것은 피보나치 수열은 재귀적인 관계를 가지고 있다는 것이다.
즉 F(N)은 F(N-1)과 F(N-2)에 의해서 결정된다.
DP의 특성 1 : 중복되는 부분 문제 (Overlapping Subproblem)
피보나치 수열이 해를 찾는 과정을 유심히 살펴보면 "큰 문제"를 찾기 위해 여러 "부분 문제"를 반드시 풀어야 하고 "부분 문제"는 반드시 중복해서 나타난다는 점이다.
예를 들어 F(4)를 구하기 위해선 "부분 문제" F(3)과 F(2)의 해를 찾아야 하고 F(3)은 다시 쪼개져 F(2)와 F(1)의 해를 찾아야 한다.
• F(4) = F(3) + F(2)
┗ F(4) = ( F(2) + F(1) ) + F(2)
이처럼 중복되는 부분 문제(Overlapping Subproblem)는 분할 정복과 동적 프로그래밍의 가장 큰 차이다.
분할 정복은 "큰 문제"가 "유니크한 부분 문제"로 나뉘지만 동적 프로그래밍은 "부분 문제"가 반복적으로 등장한다.
DP의 특성 2 : 최적 부분 구조(Optimal Substructure)
피보나치 수열에서 "부분 문제"의 해가 "큰 문제"에 영향을 받지 않고 언제나 동일하다.
F(4)를 구하기 위한 F(2)의 해를 구하는 방식과 그 결괏값이
F(3)을 구하기 위한 F(2)의 그것과 동일하다는 의미이다.
이처럼 "큰 문제"의 해를 찾기 위한 연산과 "부문 문제"의 해를 찾기 위한 연산이 동일해야 하며 "부분 문제"의 해를 조합해 "큰 문제"의 해를 찾을 수 있는 구조를 최적 부문 구조(Optimal Substructure)라고 한다.
쉽게 정리하면 "큰 문제"의 해는 "부분 문제"의 조합으로 찾을 수 있으며 문제의 해는 동일한 연산으로 수행되어야 한다.
동적 프로그래밍 : 한 단계 더 생각해 보기 (메모이제이션)
코딩 테스트 혹은 프로그래밍 문제를 해결하려 할 때 동적 프로그래밍을 적용하려면 두 특성을 만족해야 한다.
하지만 잘 생각해 보면 동적 프로그래밍이 가진 고질적인 문제점도 존재한다. 중복되는 "부분 문제"들이 반복해서 등장하고 동일한 문제를 여러 번 계산해야 한다.
앞서 설명한 F(4)를 구하는 과정만 봐도 F(2)를 두 번 계산해야 한다는 문제점이 있다.
• F(4) = F(3) + F(2)
┗ F(4) = ( F(2) + F(1) ) + F(2)
아래 코드만 실행해봐도 결괏값이 나오기까지 꽤 오랜 시간이 걸린다.
// C++ Code
#include <iostream>
using namespace std;
int Fib(int x)
{
if (x == 1)
return 1;
if (x == 2)
return 1;
return Fib(x - 1) + Fib(x - 2);
}
int main()
{
cout << Fib(40);
}
이러한 문제를 해결하기 위해 동적 프로그래밍에선 중복된 계산을 피하고자 이전에 구한 "부문 문제"의 해를 메모리에 저장해두며 이를 메모이제이션(Memoization)이라고 한다.
메모이제이션이 적용된 Fib(5)를 계산하는 과정은 다음과 같다.
• Fib(5) = Fib(4) + Fib(3)
┗ Fib(5) = (Fib(3) + Fib(2)) + Fib(3)
┗ Fib(5) = (Fib(2) + Fib(1)) + Fib(2) + Fib(3)
┗ Fib(3)의 해(2)를 메모리에 저장하면 Fib(3)의 "부분 문제"를 다시 풀지 않아도 된다.
#include <iostream>
using namespace std;
int _dp[50];
int Fib(int x)
{
if (x == 1) return 1;
if (x == 2) return 1;
if (_dp[x] != 0)
return _dp[x];
return _dp[x] = Fib(x - 1) + Fib(x - 2);
}
int main()
{
cout << Fib(40);
}
마치며
피보나치 수열뿐만 아니라 동적 프로그래밍이 적용되는 몇 가지 문제를 더 소개하고 싶지만 언제나 그렇듯 글이 길어지면 뒤로 갈수록 내용이 부실해지는 것 같아서 일단 여기서 끝내려 합니다.
나중에 시간이 되면 동적 프로그래밍으로 해결할 수 있는 문제를 포스팅하겠습니다.
