DP의 기본에 대해서...

이번에는 DP(Dynamic Programing)에 대해 말해보려고 한다. 사전적으로 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 동적 계획법에 대해서는 딱히 내용은 없지만 할 말이 많아서 차근 차근 진행해 보려고 한다.

0. DP란?

위에서 서술한 것 처럼 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 간단하게 예시를 들어보자. 피보나치 수의 100번째 수를 구해야 한다고 해보자. 하지만 P(100)=P(99)+P(98)이기 때문에 우리는 피보나치 수의 100번째 수를 구하는 대신 99번째와 98번째 수를 구하는 것으로 대체할 수 있다. 이런 식으로 더 부분 문제에 대한 답을 구해 놓아 이를 통해 더 큰 문제의 답을 계산 하여 구하는 과정을 반복하여 최종 답까지 도달하는 것이다. 

1. DP 문제들은...

N이 주어지고 (가끔 M과 N개의 정수들도) 답을 정수로 출력하며 특히 1e9+7로 나눈 나머지를 출력해야 하면 DP이다.  라는 말이 사실 맞는 말 일수도 있을 정도로 처음 DP라는 것을 접하는데에 있어 몇 개 풀어보다 보면은 어떤 문제들이 DP를 써야 하는 문제인지 쉽게 알 수 있다. 하지만 문제들이 점점 어려워질수록 추가적인 테크닉, DP식 세우기가 점점 어려워지며 가끔씩 정말 DP라고는 생각이 안되는 곳에서 DP를 써야할 때가 나오기도 한다. 
그렇다면 언제 DP를 쓸 수 있을까? 내가 내린 결론은 어떤 항을 구하기 위한 전 항들을 완벽히 구할 수 있고, 그 항들을 이용하여 정의에 맞는 현재 항이 깔끔하게 정의가 될 때이다. 지금 당장은 공감이 안 될지 몰라도 문제를 풀다보면 공감이 될 것이라고 생각한다. (이 글 참고) 이 말은 내가 어떻게 DP식을 세워 나갈지에도 도움이 될 것이다. 

2. DP문제를 풀어가는 과정

보통 문제를 풀어가는 과정은 크게 두 과정으로 나뉜다. 아이디어&생각 그리고 구현. DP문제는 전자에 많이 치중된 느낌이다. 구현은 생각보다 짧을 때가 많다. 그럼 전단계가 어떻게 나뉘어져 있는지 알아보자.

1. 문제 탐색하기
특히 DP 일수록 문제에 대한 이해도와 관찰이 중요하다. DP 문제에서의 핵심은 DP식을 세우는 것인데 그 DP식을 세우는 과정이나 그 값을 구하기 위한 과정에서의 정당성과 시간복잡도는 내가 문제에서 관찰을 한 사실로부터 나온다.

2. DP식 세우기 
DP문제를 해결하는데 있어 가장 중요한 과정이 DP식을 세우는 것이다. dp[i]=i까지~~ 또는 dp[i][j]=i까지 j개로 ~~ dp[i][j]=i부터 j까지~~ 등 다양한 방식으로 세울 수가 있고 이는 문제의 특징에 따라 달라질 것이다. 이 부분은 재능과 노력의 콜라보로 이루어지는 것 같다. 어려운 문제에서 빠르게 DP식을 잡아내는 것은 어느정도 재능이 있고, 많은 문제를 경험 해 봤어야 가능한 일이다.

3. 검증 및 구현
자신이 세운 DP식이 잘 들어맞는지, 시간복잡도는 괜찮은지 확인을 해야한다. 시간제한이 걸린다면 상황에 따라 여러가지 테크닉들로 시간복잡도를 향상 시킬 수 있다. 그렇게 전체적인 틀이 짜였으면, 구현을 하면 된다. 어려운 테크닉을 사용하지 않는 이상 보통은 구현이 윗 단계들 보다 어렵지는 않다.

3. DP문제를 공부하기

위에서 말했다시피 다양한 자료구조, 알고리즘, 테크닉들을 잘 몰라도 시작할 수 있는것이 DP이다. 그런데 DP는 큰 대회에서도 무조건 출제될만큼 정말 중요한 기술이라 꼭 많은 문제를 풀어보면서 익혀야한다. 꾸준히 해서 DP가 자신있다면 이득을 볼 기회가 정말 많다. 하지만 DP에만 너무 몰두하다가는 구현력이 떨어질 수 있으니 조심해야한다.

4. 추천하는 문제들

사실 나도 좋은 문제를 완벽히 알고있지는 않다. 그래도 DP는 꽤나 많은 문제를 풀어봤다고 이야기 할 수 있고, 문제 추천도 많이 했다. 그래서 좋은 DP문제들을 모아 따로 글을 작성했다. 이 글 참고