유명한 문제인 하노이 탑 문제를 풀어본다 생각해보자. 규칙은 다음과 같다.
원판의 개수가 적을 때는 머리속으로 연상하면서 풀 수 있다. 하지만 원판의 개수가 늘어난다면 어떻게 될까? 원판의 개수가 10개, 20개 혹은 100개라면? 더 이상 상상만으로 풀기 어려워진다. 따라서 수가 늘어난다면 알고리즘을 사용하여 문제를 해결해야한다.
알고리즘을 작성/사용하려면 일단 문제 속에 숨겨진 규칙을 찾아야 한다. 예시로 보여준 하노이 탑에도 규칙이 숨겨져있는데, 작은 원판 위에 큰 원판이 올라올 수 없다 에서 찾을 수 있다. 이 규칙 때문에 5 크기의 원판을 3번째 기둥으로 움직이려면 5 보다 작은 크기의 원판이 모두 2번째 기둥에 있어야 한다. 따라서 5개의 원판이 있다면 하노이 탑 문제의 답은 1 + 4개의 원판을 움직이는 데 소요되는 시간 x 2 가 된다. (4개 원판을 2번째 기둥으로 이동 → 5 원판 3번째 기둥으로 이동 → 나머지 4개 원판을 3번째 기둥으로 이동)
이렇게 하나의 문제를 풀기 위해 그보다 작은 경우 혹은 과거의 경우를 이용하여 문제를 푸는 방법이 동적 계획법(Dynamic propgramming)이며 동적 계획법은 최적화를 위해 메모이제이션 기법(중복된 연산을 없애기 위해 이전 기록을 저장하는 기법)을 사용한다.
dp는 2가지 방법으로 구현 가능하다. 하나는 재귀를 이용해 구현하는 방식이고 하나는 점화식을 이용하여 반복문으로 구현하는 방식이다. dp에 대해서 많이 접해봤다면 2가지 방법 모두 상관 없겠지만(스택을 고려해야하는 극한의 상황일 경우는 다를 것이다) 어색하다면 재귀를 이용하여 풀어보는 것을 추천한다. 예를 들어 위의 하노이 탑의 문제를 구현한다 해보자.
재귀를 이용한다면 다음과 같아진다.
int dp[1001] = {0,};
int solve(int size)
{
if (dp[size] != 0)
return (dp[size]);
else
return (solve(size - 1) * 2 + 1);
}
int main()
{
int N;
dp[1] = 1;
solve(N);
}
재귀로 푼다면 찾아낸 규칙을 바로 적용해 볼 수 있다. 반복문으로 구현한다면 점화식을 작성해야 한다.
int solve(int size)
{
int index;
int dp[1001];
index = 2;
dp[1] = 1;
while (index <= size)
{
dp[index] = dp[index - 1] * 2 + 1;
index++;
}
return (dp[size]);
}
int main()
{
int N;
solve(N);
}
dp[index] = dp[index - 1] * 2 + 1 이 부분이 점화식에 해당하며, dp에서 가장 어려운 부분이 이 점화식을 찾는 것이다. dp를 잘하려면 어떻게 해야할까요? 라는 질문에 자세히 답하고 싶지만 아쉽게도 마땅히 답할 내용이 생각나지 않는다. (작성자가 dp를 뛰어나게 잘하지도 못 한다는 이유도 있다…) 반대로 질문해 보겠다. 수학 문제를 잘 푸려면 어떻게 해야할까? 어떤 문제가 어떤 공식을 사용할 것인지 까지는 문맥을 찾아보면서 알아낼 수 있겠지만(사실 이것 또한 중요하다. greedy문제인지 dp문제인지 햇갈리는 경우가 있다) 해당 공식을 어떻게 사용하는지는 문제를 푸는 사람의 몫이다.
dp의 경우는 점화식 문제를 푼다 생각하면 된다. 그렇다면 점화식을 잘 찾는 방법이란게 있을까? 아쉽게도 점화식을 찾는 과정에 공식은 없기에 답해줄 수 없다. 그래도 답해보자면 많이 풀어보되, 위의 규칙을 찾는 과정에 집중해야 할 것이다. 문제를 푸는 과정에서 어떤 과정이 반복된다는 사실을 찾거나, 해당 문제를 풀기 위해 어떤 시점, 혹은 어떤 하위 값과 비교해보는지를 찾아야 한다.
다른 문제를 살펴보겠다. 백준 1904번 01문제도 하위 개념을 불러온다는 점은 동일하다.
문제의 규칙은 다음과 같다.