[개념] 동적계획법(Dynamic Programming, DP) : Algorithm
동적계획법?
- 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정
- 간단 명료하게 이 전에 부분 문제를 메모리에 기록, 한번 계산한 부분 문제를 다시 계산 X
- 규칙(점화식)을 찾는 문제
- f(n) = f(n-1) + f(n-2)처럼 작은 문제가 점점 큰 규모의 문제를 구성하는 구조
- DFS, BFS의 너무 많은 연산횟수를 줄이기 위해
- 일반적인 재귀를 사용해 작은 문제들이 여러번 반복되는 비효율적인 계산 줄일 수 있다
- 위에서 언급한 배경을 기반으로 DP는
- 큰 문제를 작은 문제로 나눌 수 있는 경우
- 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일한 경우
의 조건에서 가능하다
방식
Bottom Up, 상향식
- 반복문 이용해 작은 문제에서 큰 문제로 반복문 이용해 작은 문제에서 큰 경우로 규모 증가시키며 문제 해결하는 경우
- 주로 권장하는 방법
- 일반적으로 재귀보다 반복문이 오버헤드를 줄일 수 있어 성능이 더 좋다
Top Down, 하향식
- 큰 문제 해결하기 위해 재귀 이용해 작은 문제부터 해결하는 것
메모이제이션(Memoization)
문제 접근 방법
- DP 유형인지 파악
- 완전 탐색 알고리즘을 사용한 경우 시간이 매우 오래 걸리면 DP를 적용할 수 있는지, 중복 여부 확인
- 재귀보단 반복문 권장
분할 정복과 DP
- 분할 정복(Devide and Conquer)와 DP의 차이점은 두 알고리즘 모두 문제의 규모를 변화시켜 문제를 해결하지만 분할 정복의 경우는 규모 바꾸기 이전과 이후 문제 서로 영향 주지 않지만 DP의 경우는 문제의 규모가 변화했을 때 이전 문제가 현재 문제에 영향을 끼친다
- 이는 DP의 경우는 한번 해결된 문제를 다시 접근하는 작업 존재
- 물론 메모리제이션을 이용해 접근해도 바로 종료하는 방법으로 개선