💡 다이나믹 프로그래밍 (Dynamic Programming)
👉 동적 계획법
👉 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식이다.
👉 중간 계산 결과를 기록하기 위한 메모리가 필요하다.
👉 한 번 계산한 부분을 다시 계산하지 않기 때문에 속도가 빠르다.
💡 다른 알고리즘과의 차이점
👉 분할 정복과의 차이
- 분할 정복은 부분 문제가 중복되지 않는다.
- DP는 부분 문제가 중복되어 재활용에 사용된다.
👉 그리디 알고리즘과의 차이
- 그리디 알고리즘은 순간의 최선을 구하는 방식이다. (근사치를 구한다.)
- DP는 모든 방법을 확인 후 최적해를 구하는 방식이다.
💡 다이나믹 프로그래밍 예시
👉 피보나치 수열
- 피보나치 수열을 기본 재귀로 풀게 되면
f(n) = f(n-1) + f(n-2)
ex. f(5) = f(4) + f(3) 을 구하기 위한 연산들을 하고 f(3)을 다시 구하려면
f(3) = f(2) + f(1) 연산을 다시해줘야 한다.
따라서 n의 수가 높아지면 해야하는 연산도 많아진다. - 피보나치 수열을 DP를 적용해서 풀게 되면
f(n) = f(n-1) + f(n-2)
ex. f(5) 를 구하기 위한 연산들을 모두 기록해놓기 때문에 f(3)을 다시 구할 때 재귀 풀이처럼 다시 연산을 하는 것이 아닌, 기록된 정보를 가져온다.
메모리는 필요하지만 중복된 연산을 하지 않기 때문에 속도가 빠르다.
💡 다이나믹 프로그래밍 방법
👉 타뷸레이션 (Tabulation)
- 상향식 접근 방법 (Bottom Up)
- 작은 하위 문제부터 풀면서 올라간다.
- 모두 계산하면서 차례대로 진행하는 방법
👉 메모이제이션 (Memoization)
- 하향식 접근 방법 (Top Down)
- 큰 문제에서 하위 문제를 확인해가면서 진행한다.
- 계산이 필요한 순간에 계산하면서 진행하는 방법
BE