동적 프로그래밍(Dynamic Programming)의 개념

DP 문제를 풀다가 DP에 대한 이해가 부족한 것 같아서 글로 정리해본다.

Dynamic Programming

동적 프로그래밍이란 큰 문제를 작은 문제로 분할하여 문제를 푸는 방법이다. 이 용어는 리처드 벨만이 처음 사용했는데, 이름에 큰 의미는 없다. 그냥 멋있어서 사용했다. 아무튼간에 이 방법을 사용하는 이유는, 큰 문제가 작은 문제를 포함하는 구조를 갖고 있을 때, 작은 문제를 알면 큰 문제의 정답을 빠르게 구할 수 있다는 점이다.

 

 

 

위의 코드를 한 번 읽어보자.

1 = 1

2 = 2 + 1

3 = 3 + 2 + 1

...

100 = 100 + 99 + 98 + ... + 3 + 2 + 1

이런 식으로 구하는데, 잘 보면 3 = 3 + 2 + 1을 구할 때, 여기서 2 + 1은 sum(2)와 동일하므로 이미 풀었던 문제에 해당한다. 그런데 sum(3)을 풀 때, sum(2)를 처음부터 다시 구해서 쓰므로 sum(n)의 시간복잡도는 $O(n) $이 된다.

 

하지만 위의 코드에서는 문제를 푼 후에, 정답을 따로 저장해둬서

sum(n) = n + d[n-1]이 된다. 따라 sum(n-1)을 미리 구했다면 sum(n)을 $O(1) $만에 답을 구할 수 있으므로 효율적이다.

이런식으로 DP는 큰 문제 안에 작은 문제가 포함되어있을 때, 작은 문제의 정답으로 큰 문제의 정답을 구할 수 있다.

 

DP로 풀기 위한 조건

1. 큰 문제를 작은 문제로 분할할 수 있다.

2. 작은 문제의 정답을 이용하여 큰 문제를 해결할 수 있다.

 

따라서 DP 문제를 풀 때는, 무작정 DP를 쓸 게 아니라 이 문제를 어떻게 더 작은 문제로

분할할 수 있을지를 생각해야한다!