# 혼자 공부하고 정리하는 블로그
"동적 프로그래밍(Dynamic Programming, DP)"은 복잡한 문제를 해결하기 위해 문제를 더 작은 부분 문제로 나누고, 그 결과를 재사용하여 효율적으로 문제를 푸는 알고리즘 기법. 동적 프로그래밍을 사용하는 주요 이유는 중복되는 계산을 피하고 계산 속도를 향상시키기 위해서임.
1. 중복 계산 방지
많은 문제에서 동일한 부분 문제가 여러 번 반복되며 등장하는데, 이를 메모이제이션(memoization)이나 타뷸레이션(tabulation)을 통해 결과를 저장하고 재사용함으로써 중복된 계산을 줄일 수 있다. 예를 들어, 피보나치 수열을 재귀적으로 계산하는 경우, 동일한 값을 여러 번 계산하게 됨. 이를 동적 프로그래밍을 사용하면 한 번 계산한 값을 저장해 놓고 필요할 때 다시 사용하는 방식으로 처리할 수 있음.
밑에 그림처럼 피보나치 수열을 단순한 재귀로 계산하는 경우 각 값이 중복해서 여러 번 계산됨. 하지만 동적 프로그래밍을 사용하면 한 번 계산된 값을 저장하고 재사용하기 때문에 시간 복잡도가 획기적으로 줄어듬.
*피보나치 수열이 뭔지는 링크 참고 : https://terms.naver.com/entry.naver?docId=3338362&cid=47324&categoryId=47324
fib(3) 을 예로들면, 재귀로 계산할경우 3번의 중복 계산이 필요함. 전체로 보면 중복 계산이 많음 하지만 2번째 그림처럼 실제로는 저정도만 있으면 풀 수 있음
2. 문제를 더 작은 문제로 분할하여 해결
동적 프로그래밍은 문제를 작은 하위 문제로 나누어 그 결과를 바탕으로 더 큰 문제를 해결한다. 이 과정에서 하위 문제의 결과를 저장해 두고, 큰 문제를 해결할 때 이 결과를 사용.
최단 경로 문제에서 각 경로의 부분 경로를 기억해 두고, 이를 사용하여 전체 경로를 계산하는 방식으로 문제를 해결할 수 있음.
3. 시간 복잡도 감소
동적 프로그래밍을 사용하면 재귀적인 계산에서 발생하는 시간 복잡도 문제를 크게 줄일 수 있다. 재귀적인 방법으로 해결하는 문제에서 많은 중복 계산이 발생할 수 있지만, 동적 프로그래밍을 사용하면 중복된 계산을 피하고 시간 복잡도를 지수형에서 다항식 시간으로 줄일 수 있음.
피보나치 수열을 단순 재귀로 계산할 경우 시간 복잡도가 O(2^n)이지만, 동적 프로그래밍을 사용하면 O(n).
4. 공간 복잡도 개선 가능성
동적 프로그래밍은 때로는 메모리 사용량도 최적화할 수 있다. 문제에 따라서는 메모이제이션을 통해서 저장 공간을 더 효과적으로 관리할 수 있고, 불필요한 중복 저장을 피할 수 있다. 특히 타뷸레이션 방식에서는 필요한 하위 문제의 결과만을 저장하며, 이전 결과를 단계적으로 갱신함으로써 메모리 사용을 줄일 수 있다.
5. 결정 문제에서 최적의 해를 보장
동적 프로그래밍은 일반적으로 최적의 해를 보장한다. 예를 들어, 최단 경로 문제, 배낭 문제, 게임 이론 등의 결정 문제에서 동적 프로그래밍을 사용하면 문제의 구조적 특성(예: 최적 부분 구조)을 활용해 최적의 해를 구할 수 있다. 이는 그리디 알고리즘이나 재귀적인 방법과는 달리 항상 최적 해를 찾을 수 있다는 장점이 있다.
※ 타뷸레이션과 메모이제이션의 차이점:
• 메모이제이션은 하향식 접근(재귀 호출)으로 문제를 풀고, 이미 계산한 결과를 캐싱해 중복 계산을 피하는 방식이다.
• 타뷸레이션은 상향식 접근으로, 작은 하위 문제부터 해결하면서 테이블에 저장해가며 문제를 푼다.
둘 다 중복 계산을 피하고 효율성을 높인다는 점에서 공통점이 있지만, 타뷸레이션은 재귀 호출이 없고 상향식이라는 점이 다르다.
피보나치수 구하는 코드
1) 재귀적 방법
2) 메모이제이션
3) 타뷸레이션
※ 재귀적 방법이 유용한 예와 유용하지 않은 예:
• 유용한 예 : 퀵정렬, 병합정렬 등 정렬 알고리즘, factorial, DFS
• 유용하지 않은 예 : 피보나치 수열
※ 동영상 설명은 위 그림의 youtube 참고