📌 Dynamic Programming
탐욕 알고리즘(Greedy)과 함께 언급하는 알고리즘으로, 줄임말로 DP 라고 하는 이 알고리즘은, 탐욕 알고리즘과 같이 작은 문제에서 출발한다는 점은 같다. 그러나, 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, DP는 모든 경우의 수를 조합해 최적의 해법을 찾는다.
즉, 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결한다. 하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 다시 말해, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍이다.
다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있다.
- Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
- Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.
📌 Overlapping Sub-problems
큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다.
이 가정의 대표적인 예시로 피보나치 수열을 들 수 있다.
피보나치 수열은 첫째와 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합과 같은 수열이다.
function fib(n) {
if(n <= 2) {
return 1;
};
return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...[코드] 재귀함수로 구현한 피보나치 수열
이 함수의 계산 과정을 그림으로 살펴보면, 다음과 같다.
[그림] 피보나치 수열 모식도
그림에서 본 것을 토대로, 7번째 피보나치 수 fib(7) 를 구하는 과정은 다음과 같다.
fib(7) = fib(6) + fib(5)
fib(7) = (fib(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)
...[코드] 피보나치 수열 예시
피보나치 수열은 위 예시처럼 동일한 계산을 반복적으로 수행해야 한다.
fib(5) 는 두 번, fib(4) 는 세 번, fib(3) 은 다섯 번의 동일한 계산을 반복한다.
이렇게, 작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때, 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족한다.
그러나 이 조건을 만족하는지 확인하기 전에, 한 가지 주의해야 할 점이 있다. 주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 한다.
📌 Optimal Substructure
이 조건에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미한다. 주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 한다. 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있다.
이 가정의 대표적인 예시로 최단 경로를 찾는 문제를 들 수 있다.
A에서 D로 가는 최단 경로를 찾아야 합니다. 다음과 같이 각 지점이 있고, 한 지점에서 다른 지점으로 갈 수 있는 경로와 해당 경로의 거리는 다음과 같다.
[그림] 방향성 그래프 예시
-
A → D로 가는 최단 경로 : A → B → C → D
-
A → C로 가는 최단 경로 : A → B → C (A → B → E → C 가 아닙니다.)
-
A → B로 가는 최단 경로 : A → B
정리해보면 A에서 D로 가는 최단 경로는 그것의 작은 문제인 A에서 C로 가는 최단 경로, 그리고 한 번 더 작은 문제인 A에서 B로 가는 최단 경로의 파악할 수 있다. 이렇게 Dynamic Programming을 적용하기 위해서는, 작은 문제의 최적 해법을 결합하여 최종 문제의 최적 해법을 구할 수 있어야 한다.
