동적 계획법(Dynamic Programming)

DP, 즉 다이나믹 프로그래밍(동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

동적 계획법의 사용 조건

DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.

Overlapping Subproblems(겹치는 부분 문제)
DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다.
그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
Optimal Substructure(최적 부분 구조)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다!

Bottom-Up 방식

이름에서 보이듯이, 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.

메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자. Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.
Top-Down 방식

이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

피보나치의 예시처럼, f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯, n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.

이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization 이라고 부른다.

실제로 피보나치를 재귀로 구현하면 O(2^n)만큼 걸리지만, DP를 이용하면 O(N)으로 해결 가능하다. 참고 링크

[요약]
Bottom-up : 작은 문제부터 차근차근 구하는 방법(해결 용이, 가독성 떨어짐)
Top-down : 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법(재귀 방식)(가독성 굳, 코드 빡셈)

그럼, 어떤 경우에 DP를 사용해서 구현해야할까?
정답은 '몰?루' 이다.

그래서 DP를 적용시키기 전에 다음과 같은 과정을 거치는 것이 좋다.