앞서 말하지만 작성자도 dp를 잘하지 못한다. 이 글은 작성자가 dp 문제를 풀 때 어려움을 겪었던 부분에 대해서 말해보고자 한다.
유명한 문제인 하노이 탑 문제를 풀어본다 생각해보자. 규칙은 다음과 같다.
•
목표는 모든 원판을 다른 기둥으로 옮길 때까지의 이동 횟수를 구하는 것이다
•
작은 원판 위에 큰 원판이 올라올 수 없다
•
한 번에 1개의 원판만 옮길 수 있다
원판의 개수가 적을 때는 머리속으로 연상하면서 풀 수 있다. 하지만 원판의 개수가 늘어난다면 어떻게 될까? 원판의 개수가 10개, 20개 혹은 100개라면? 더 이상 상상만으로 풀기 어려워진다. 따라서 수가 늘어난다면 알고리즘을 사용하여 문제를 해결해야한다.
알고리즘을 작성/사용하려면 일단 문제 속에 숨겨진 규칙을 찾아야 한다. 예시로 보여준 하노이 탑에도 규칙이 숨겨져있는데, 작은 원판 위에 큰 원판이 올라올 수 없다 에서 찾을 수 있다. 이 규칙 때문에 5 크기의 원판을 3번째 기둥으로 움직이려면 5 보다 작은 크기의 원판이 모두 2번째 기둥에 있어야 한다. 따라서 5개의 원판이 있다면 하노이 탑 문제의 답은 1 + 4개의 원판을 움직이는 데 소요되는 시간 x 2 가 된다. (4개 원판을 2번째 기둥으로 이동 → 5 원판 3번째 기둥으로 이동 → 나머지 4개 원판을 3번째 기둥으로 이동)
이렇게 하나의 문제를 풀기 위해 그보다 작은 경우 혹은 과거의 경우를 이용하여 문제를 푸는 방법이 동적 계획법(Dynamic propgramming)이며 동적 계획법은 최적화를 위해 메모이제이션 기법(중복된 연산을 없애기 위해 이전 기록을 저장하는 기법)을 사용한다.
그렇다면 왜 dp는 어렵게 느껴질까?
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);
}
C++
복사
재귀로 푼다면 찾아낸 규칙을 바로 적용해 볼 수 있다. 반복문으로 구현한다면 점화식을 작성해야 한다.
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);
}
C++
복사
dp[index] = dp[index - 1] * 2 + 1 이 부분이 점화식에 해당하며, dp에서 가장 어려운 부분이 이 점화식을 찾는 것이다. dp를 잘하려면 어떻게 해야할까요? 라는 질문에 자세히 답하고 싶지만 아쉽게도 마땅히 답할 내용이 생각나지 않는다. (작성자가 dp를 뛰어나게 잘하지도 못 한다는 이유도 있다…) 반대로 질문해 보겠다. 수학 문제를 잘 푸려면 어떻게 해야할까? 어떤 문제가 어떤 공식을 사용할 것인지 까지는 문맥을 찾아보면서 알아낼 수 있겠지만(사실 이것 또한 중요하다. greedy문제인지 dp문제인지 햇갈리는 경우가 있다) 해당 공식을 어떻게 사용하는지는 문제를 푸는 사람의 몫이다.
dp의 경우는 점화식 문제를 푼다 생각하면 된다. 그렇다면 점화식을 잘 찾는 방법이란게 있을까? 아쉽게도 점화식을 찾는 과정에 공식은 없기에 답해줄 수 없다. 그래도 답해보자면 많이 풀어보되, 위의 규칙을 찾는 과정에 집중해야 할 것이다. 문제를 푸는 과정에서 어떤 과정이 반복된다는 사실을 찾거나, 해당 문제를 풀기 위해 어떤 시점, 혹은 어떤 하위 값과 비교해보는지를 찾아야 한다.
문제의 규칙은 다음과 같다.
•
00과 1을 이용하여 일정 길이의 문자열을 만들 수 있는 경우의 수를 구하라.
문자열의 길이가 10이라 해보자, 그럼 하위 개념은 어떤 것일까? (이런 과정을 연습해야 한다)
경우는 단 두가지 뿐이다. 00을 붙이는 경우와 1을 붙이는 경우, 그리고 전자의 경우는 붙이기 위해 2칸이 필요하고 후자의 경우 붙이기 위해 1칸이 필요하다. 따라서 길이가 10인 문자열을 만드는 경우는 길이가 8인 경우 + 길이가 9인 경우다.
길이가 8인 경우 11을 붙일 수 있지 않나? 라고 의문이 들 수 있다. 하지만 11을 붙이는 경우는 길이가 9인 경우(그 중 마지막이 1인 경우)에 1을 붙이는 것과 동일하다. 따라서 해당 상황을 따진다면 중복될 것이다.
이를 점화식으로 만든다면
dp[n] = dp[n -1] + dp[n - 2]가 되며 코드로 작성한다면 다음과 같다.
#include <iostream>
int main()
{
int N;
int dp[1000001];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
std::cin >> N;
for (int i = 4; i <= N; i++)
{
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
}
std::cout << (dp[N]);
}
C++
복사
결론은 많이, 그리고 다양한 문제를 풀어봐야 한다
이렇듯 문제에 따라서 dp의 하위 개념은 어떤 숫자일 수도, 어떤 시점, 문자열의 일부, 맵의 일부, 혹은 그래프의 경우는 정점의 위치가 하위 개념이 될 수 있다. 어떤 하위 개념을 설정하는 지에 따라서 저장할 배열의 구조가 달라질 수 있고 실패, 성공 유무도 나뉘기 때문에 dp를 잘하기 위해선 다양한 문제를 많이 풀어보는 수 밖에 없는 듯 하다.
