[모각코] DP 1
1. DP
DP는 다이나믹 프로그래밍의 약자이다. 다이나믹 프로그래밍은 하나의 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결하는 데 사용하는 것이다. 즉 큰 문제를 나누어 작은 문제로 만들고 작은 문제들의 답을 활용하여 큰 문제를 해결하는 방식이다.
큰 문제를 작은 문제로 나누어서 해결한다는 점에서 재귀와 비슷하다고 볼 수 있지만 DP의 경우 작은 문제들의 답을 저장하여 재사용한다는 점에서 차이를 보인다.
2. 사용 조건
DP는 적용하기 위해서 조건이 있다.
- 겹치는 부분 문제
- 최적 부분 구조 총 두 가지를 만족하는 문제에서 DP를 적용할 수 있다.
겹치는 부분 문제는 큰 문제를 나누었을 때 동일한 작은 문제들이 반복하여 나타나는 경우이다. 작은 문제들의 결과를 저장하여 재계산 없이 처리할 수 있어야 하기 때문에 작은 문제들이 반복해서 나타나지 않는다면 DP를 사용하기에 적절하지 않다.
최적 부분 구조는 부분 문제의 최적 결과 값을 사용해서 전체 문제의 최적 결과를 낼 수 있는 경우이다. 빌드업 형식으로 가장 작은 문제부터 큰 문제로 올라가면서 최적 결과를 쌓아가는 형태로 해결할 수 있다. 하지만 이 역시 작은 문제에서의 최적 결과가 전체 문제에서의 최적 결과에 포함되지 않는 경우 사용할 수 없다.
3. DP 적용
첫 번째로는 DP를 적용할 수 있는 문제인지 파악하는 것이다. 위의 두 가지 사용 조건을 만족하는지 판단해 결정한다.
두 번째로는 문제의 변수를 파악한다. 변수에 따라 값이 달라지고, 해당 값들을 저장해 두었다가 재사용한다.
세 번째는 변수 간의 관계식을 만드는 것이다. 수열을 공부할 때 배웠던 것 처럼 점화식을 세우는 것과 같다. 실제로 DP로 해결하기 좋은 문제 중 피보나치 수열도 f(n) = f(n-1) + f(n-2)라는 점화식을 가진다.
네 번째로는 결과값을 저장한다. memorization이라고도 한다. 작은 문제들의 결과값을 기억하고 큰 문제를 해결할 때 작은 문제의 결과값이 필요할 경우 기억해둔 값을 재사용한다. 이렇게 되면 큰 문제를 해결하려고 작은 문제를 다시 해결할 이유가 없어지며 이것이 DP의 가장 큰 장점이다.
마지막으로 기저 상태를 파악한다. 기저 상태란 가장 작은 문제의 상태이다. 수열의 초항처럼 가장 작은 문제의 경우 다른 문제의 결과값을 재사용하여 구할 수 없기 때문에 직접 계산하여 알아내야 하는 경우가 많다.
4. 구현
DP를 구현하는 방법은 크게 두 가지가 있다. Top-down 방식과 Bottom-up 방식이다. Bottom-up 방식은 DP 테이블이라 불리는 문제들의 결과값 배열을 가장 작은 문제부터 채워 나가며 결과값을 누적시켜 문제를 해결하는 방식이다.
Top-down 방식의 경우 기저 상태에서 출발하는 것이 아닌 가장 큰 문제에서부터 호출해 내려가 가장 작은 문제까지 간다. 이후 결과 값을 재귀를 통해 전이시켜 재사용한다. 피보나치 수열에서의 경우를 예로 들면 f(5)를 구하기 위해 f(1)과 f(2)까지 호출해 내려가고, 재귀를 통해 함수를 탈출하며 f(5)까지 올라오면서 저장해 둔 값들을 재사용한다.
5. 마무리
DP에 대해 단순히 테이블을 채우고 반복되는 문제에 사용한다고만 막연히 알고 있었지만 어떤 상황에서 적용할 수 있는지와 구체적으로 어떻게 구현해 나가야 하는지에 대한 이해가 없었다. 개념을 다시 정리하며 스쳐가듯 알고 있었던 부분을 알 수 있게 되었고 앞으로 DP 문제를 푸는 데 많은 도움이 될 거라고 생각한다. 다음 포스팅부터는 실제로 DP 문제를 풀며 오늘 공부한 것을 적용해 볼 것이다.