첫 게시물로 중요한 알고리즘 기법인 동적 계획법(다이나믹 프로그래밍)에 대한 내용을 적어 보려 한다.
Dynamic Programming - Technique for solving problems with overlapping subproblems
지난 학기에 수강했던 고려대학교 정보대학 이도길 교수님의 알고리즘 수업 자료에서는 DP의 정의를 위와 같이 설명한다. 즉, 동일한 유형의 subproblem들을 해결하면서 이것을 이용해 원래 문제를 해결하는 것이 다이나믹 프로그래밍 기법이다. 더 구체적으로 얘기하자면, DP에서는 각 subproblem을 해결하고 그 결과를 table에 기록해 뒀다가, 원래 문제의 해결에 이를 활용하는 방법을 제안한다.
다이나믹 프로그래밍에서 핵심적으로 사용되는 기술로 메모이제이션(memoization)이라는 기법이 있다. 이는 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 아래의 링크는 위키백과에 나와 있는 메모이제이션의 정의이다.
https://ko.wikipedia.org/wiki/메모이제이션
Dynamic programming 기법을 사용하여 풀 수 있는 문제 유형은 크게 두 가지가 있다.
- Overlapping subproblems
- Optimal substructure :
각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우, '최적 부분 구조 조건'을 성립한다고 말한다. 즉, "큰 문제의 답에는 작은 문제의 답이 들어 있다"라고 생각하면 될 듯하다.
지금까지 늘어 놓은 막연한 개념 정리를 보충하기 위해, 한 가지 예제를 제시해 보려 한다.
백준 #1003, "피보나치 함수"
https://www.acmicpc.net/problem/1003
피보나치 수는 DP로 해결 가능한 대표적인 문제 유형 중 첫 번째인 Overlapping subproblems의 대표적인 예시이다. 이 문제는 재귀를 사용한 일반적인 피보나치 수 알고리즘에서 fibonacci(0)과 fibonacci(1)이 각각 몇 번 호출되는지를 요구한다. 시간초과를 피하려면, "메모이제이션"을 이용해 이전 숫자들의 0 호출 횟수와 1 호출 횟수를 기록해 두고, 이것을 활용해 답을 도출하는 방식으로 접근해야 한다.
정답 코드 (나의 예시)
#include <iostream>
int zero[41];
int one[41];
int main(void) {
int N, T;
zero[0] = 1; zero[1] = 0;
one[0] = 0; one[1] = 1;
for(int i=2; i<41; i++) {
zero[i] = zero[i-1] + zero[i-2];
one[i] = one[i-1] + one[i-2];
}
std::cin>>T;
for(int i=0; i<T; i++) {
std::cin>>N;
std::cout<<zero[N]<<" "<<one[N]<<std::endl;
}
return 0;
}
사실 이것이 메모이제이션 기법을 올바르게 사용한 코드라고 할 수 있는지는 잘 모르겠다.(비판 및 피드백은 언제든지 환영입니다) 다만, 이 방법으로 시간을 효과적으로 줄일 수 있다는 것은 명백한 사실이다.
당분간 PS는 백준에 있는 다이나믹 프로그래밍 문제들 위주로 진행하면서, 개인적으로 기록하고 싶은 문제들은 블로그에 풀이 과정(혹은 풀이 실패 과정..)을 기록해 두려 한다. 솔브닥 스크릭을 열심히 초록색으로 칠해 보자!
