1. 개요
DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 알고리즘입니다.
한 알고리즘에 국한된 것이 아닌, 알고리즘을 설계하는 방법이나 접근 방식을 나타냅니다.
문제 풀이 방식의 하나라고 볼 수 있습니다. 이를 알고리즘 설계 기법이라고 합니다.
🚩 알고리즘 설계 기법
- 모든 경우의 수를 구하는 완전 탐색을 하면 가장 좋겠지만, 시간 상으로 메모리 상으로 최적화가 가장 중요합니다. 그래서 다양한 설계 기법을 도입하는데요.
- 예를 들어, 분할 정복, 그리디, 백트래킹이 그 예시가 됩니다.
2. DP 사용 이유
그러면 DP는 왜 쓰고, 언제 쓰는지 알아야겠죠?
재귀적 용법과 굉장히 흡사한 DP는 단순한 재귀 사용보다, 작은 문제들이 여러번 사용되어 비효율적인 방식을 보완합니다.
가장 흔하게 재귀를 사용하는 것은 피보나치 수를 예시로 들 수 있습니다.
- 피보나치 수 : f(n) = f(n-1) + f(n-2)
f(10)을 구하기 위해서는, f(9)도 구해야 하고, f(8)도 구해야 합니다.
또한 f(9)를 구하기 위해서 더 많은 재귀함수를 호출해야합니다.
하지만 이미 수행된 작업에 대해서 기록(Memoization)을 해둔다면, 또 다시 계산할 필요 없이 중복된 값을 구할 수 있습니다.
3. DP 사용 조건
(1) 중복 부분 문제 구조(Overlapping Subproblems)
DP는 주로 중복되는 부분이 반복적으로 나타날 때, 사용이 가능하다.
따라서, 중복되는 부분에 대해서 구해두고, 기록(Memoization)해두고, 추후 중복되는 부분이 나오면 그 값을 가져와 사용할 수 있어야 하는데, 중복되는 부분이 없다면 DP를 사용할 수 없다.
(2) 최적 부분 구조(Optimal Substructure)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 이야기 합니다.
어쨌든, 작은 문제로 분할하여 문제를 푸는데, 최적의 결과를 도출했을 때, 전체 문제에서도 최적의 결과를 낼 수 있습니다.
예를 들어, 서울에서 부산을 가는데 대구를 거쳐간다고 생각합시다.
그럴때 최단 거리로 가는 방법을 고민한다고 했을때,
[서울 → 대구]의 최단 거리 + [대구 → 부산]의 최단 거리 를 구하면 [서울 → 부산]의 최단 거리를 구할 수 있다. 이 처럼, 부분 문제에서의 최적 결과 값이 전체 문제의 최적 결과를 낼 수 있는 경우가 되어야 DP를 사용할 수 있습니다.
4. 구현 방법 (Top-Down / Bottom-Up)
Top-Down
- Top-Down 방식은 전체 문제에서 시작하여, 가장 작은 문제까지 호출 한 뒤에, 작은 문제에서 해결한 값을 저장 및 기억(Memoization)을 해둡니다. 그리고 추후 큰 문제에서 기억해둔 값을 재사용하면서 문제를 해결하는 구현 방식입니다. 주로 재귀 호출을 이용하여 문제를 풀 수 있습니다.
- 또한 재귀를 사용하기 때문에 Bottom-Up보다 구조가 복잡해보이고 이해하기 어렵습니다.
Bottom-Up
- 가장 작은 문제부터 시작해서, 작은 문제를 해결하고 그 값을 저장(Tabulation)하고, 다음 문제를 순차적으로 해결하며 전체 문제까지 해결하는 구현 방식입니다. 이러한 문제 해결 특성상 반복문을 사용하는 특징이 있습니다.
- Tabulation은 사전적 정의로 도표 작성입니다. 문제 해결 방식이 표를 채우는 것과 유사해서, 붙여진 이름입니다.
- 또한 Top-Down보다 구조가 직관적이기 때문에 이해하기 쉽습니다.
5. DP 푸는 방법
DP는 알고리즘 설계 기법이기때문에, 한 분야에 국한되지 않고, 다양한 곳에 사용될 수 있습니다.
그래서 이 문제를 DP로 풀 수 있는지 알아내는 것이 중요합니다.
DP 문제를 풀 때는 다음과 같은 과정을 거치게 됩니다.
- DP로 풀 수 있는지 확인합니다.
- 문제들이 중복되어 Memoization/Tabulation 기법으로 사용하면 더 효율적인지?
- 문제들의 변수를 파악하기
- 변수간의 점화식 만들기
- 메모하기
- 기저 상태 파악하기
- 가장 작은 문제의 상태를 알아야 한다. 예를 들어 피보나치는 f(0) = 0 / f(1) = 1이다.
- 이렇게 가장 작은 문제의 상태를 저장해두어야 합니다.
