동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제들로 나누고, 각 부분 문제의 결과를 저장하여 동일한 부분 문제를 여러 번 풀지 않도록 하는 알고리즘 기법입니다. 이는 특히 중복 계산을 피함으로써 효율성을 크게 향상시키며 주로 최적화 문제에서 사용됩니다.
동적 프로그래밍의 사용 조건
1. 최적 부분 구조(Opptimal Substructure):
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복 부분 문제(Overlapping Subproblems):
동일한 작은 문제를 반복적으로 해결해야 한다
동적 프로그래밍은 메모이제이션(Memoization)과 타뷸레이션(Tabulation) 두 가지 접근 방법으로 구현될 수 있습니다.
메모이제이션(Memoization)
메모이제이션은 탑다운 방식으로 문제를 해결합니다. 즉, 큰 문제를 작은 부분 문제로 나누어 재귀적으로 해결하며, 각 부분 문제의 결과를 저장하여 중복 계산을 피합니다. 이 방법은 재귀와 함께 사용되며, 재귀 호출 중에 이미 계산된 부분 문제의 결과를 저장한 배열이나 해시맵 등을 참고합니다.
타뷸레이션(Tabulation)
타뷸레이션은 바텀업 방식으로 문제를 해결합니다. 즉, 작은 부분 문제부터 시작하여 점차 큰 문제로 확장하며 모든 부분 문제의 결과를 테이블에 저장합니다. 이는 반복문을 사용하여 구현되며, 재귀를 사용하지 않습니다.
동적 프로그래밍의 일반적인 문제 유형
동적 프로그래밍은 여러 유형의 문제를 해결하는 데 유용합니다. 다음은 동적 프로그래밍을 적용할 수 있는 몇 가지 대표적인 문제 유형입니다.
1. 최대/최소 경로 문제: 그래프나 그리드에서 특정 시작점에서 끝점까지의 최대/최소 경로를 찾는 문제 (예: 최단 경로 문제).
2. 부분 수열 문제: 주어진 배열이나 문자열에서 특정 조건을 만족하는 부분 수열을 찾는 문제 (예: 최장 증가 부분 수열).
3. 배낭 문제: 제한된 용량의 배낭에 최대 가치를 담을 수 있는 방법을 찾는 문제.
4. 기타 최적화 문제: 특정 조건을 만족하면서 최적의 결과를 찾는 다양한 문제 (예: 행렬 체인 곱셈).
동적 프로그래밍의 장점과 단점
장점:
- 중복 계산을 피하여 시간 복잡도를 크게 줄일 수 있다.
- 문제의 크기에 따라 공간 복잡도를 조절할 수 있다.
단점:
- 모든 문제에 적용할 수 있는 것은 아니다. 문제의 특성에 따라 적절히 사용해야 한다.
- 메모리 사용량이 클 수 있다. 특히, 많은 부분 문제를 저장해야 하는 경우.