📝 동적 프로그래밍이란?
특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 기법이다.
🎯 동적 프로그래밍의 특징
- 최적 부분 구조 문제에 효과적이다.
✔ 최적 부분 구조란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성된 구조를 의미한다. - 동일한 문제를 여러번 구해야 하는 문제는 메모이제이션(Memoization) 기법으로 해결한다.
✔ 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
동적 프로그래밍 조건
- Simple subproblems - 큰 문제를 작은 문제로 나눌 수 있어야 한다.
- Optimal substructure - 최적의 해를 찾는 구조를 만들 수 있어야 한다.
- Overlapping problems - 작은 문제들이 중복되어야 한다.
동적 프로그래밍 문제 해결 방법
1. Top Down
- 탑다운 방식은 말 그대로 위에서 아래로(큰 문제에서 작은 문제로) 해결해 나가는 방식이다.
- 재귀 알고리즘을 사용하는 방식이다.
- 메모이제이션 기법은 탑다운 방식일 때 사용된다.
2. Bottom Up
- 바텀업 방식은 단순히 반복문을 통해서 가장 작은 문제에서 해결해야 하는 문제에 도달할 때까지 반복한다.
동적 프로그래밍 과정
- 최적해를 구할 수 있는 구조를 정의한다.
- 최적해의 값을 재귀적으로 정의한다.
- 캐싱을 사용하는 탑다운 방식이나 바텀업 방식으로 값을 계산한다.
- 계산된 값으로 최적의 해를 구한다.
참고자료
도라에몽 암기빵