동적 계획법
동적 계획법 (Dynamic Programming)이란 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법을 말한다. 부분 문제가 반복(Overlapping Subproblem)되거나 최적 부분 구조 (Optimal Substructure)를 가진 알고리즘을 효율적으로 해결할 때 사용한다.
최적 부분 구조 (Optimal Substructure)
답을 구하기 위해 수행한 계산을 반복해야 하는 문제의 구조
동적 계획법은 알고리즘이라기보다는 어떤 문제를 풀 때 그 문제를 더 작은 문제의 연장선으로 생각하고 기존에 구한 해를 활용하는 방법을 총칭한다고 이해하는 편이 좋다.
접근 방식
1. 큰 문제를 작은 문제로 표현할 수 있다.
예로 들어 피보나치는 아래와 같이 표현할 수 있다.
$$ \begin{eqnarray} f(3) = f(2) + f(1) \\ f(4) = f(3) + f(2) \\ f(5) = f(3) + f(4) \end{eqnarray} $$
동적 계획범을 사용하기 위해서는 하나의 큰 문제를 작은 문제로 표현할 수 있어야 한다. 다른 말로 표현하면 작은 문제의 결과를 알아야 큰 문제를 해결할 수 있다.
2. 점화식
큰 문제를 작은 문제로 표현할 수 있으면 점화식(공식)으로 표현할 수 있다. 예로 들어 피보나치의 점화식은 다음과 같다.
$$ f(n) = f(n - 1) + f(n - 2) $$
즉, 큰 문제를 점화식으로 표현할 수 있기 때문에, 동적 계획법은 점화식으로 구하는 것이 핵심이라고 할 수 있다.
3. 메모이제이션
경우에 따라 2022.08.22 - [Algorithm] 메모이제이션(Memoization) 을 활용하여 효율적으로 해결할 수 있다. 메모이제이션을 적용할 때는 중복되는 연산의 결괏값을 저장하고 찾아서 사용할 수 있는 테이블이 필요하다. 테이블은 주로 리스트, HashMap을 사용한다.
풀이 방식
Bottom-up, Top-down 이라는 두 가지 방식으로 풀이할 수 있다.
Bottom-up
데이터가 들어오는 순서대로 처리하는 방식으로, 1부터 n까지 숫자를 차근차근 계산한다.
보통 반복문을 사용한 순차적인 풀이를 Bottom-up이라고 한다.
Top-down
패턴을 이용하여 처리하는 방식으로, 재귀 함수나 메모이제이션을 사용하여 사용하여 답을 찾는다.
문제 모음
동젹 계획법에 익숙해질 만한 문제 링크를 남겨둔다.
https://www.acmicpc.net/workbook/view/7836
https://won-percent.tistory.com/3
참고 문서
https://devraphy.tistory.com/627