동적 프로그래밍 (Dynamic Programming, DP)

동적 프로그래밍(Dynamic Programming, DP)

---

 

부분해를 사용하여 복잡한 문제를 더 작은 부분 문제로 나누어 해결하고, 이러한 부분 문제의 해결 결과를 저장하여

전체 문제를 해결하는 알고리즘 기법이다. 특히 중복된 부분 문제와 최적 부분 구조를 가진 문제에 쓰인다.

동적 프로그래밍의 기본 개념

1. 중복 부분 문제 (Overlapping Subproblems)
   • 문제를 해결하는 과정에서 같은 부분 문제가 여러 번 발생한다.
   • 동적 프로그래밍은 이러한 중복 계산을 피하기 위해 부분 문제의 결과를 저장한다.
2. 최적 부분 구조 (Optimal Substructure)
   • 전체 문제의 최적해는 부분 문제의 최적해로 구성된다.
   • 큰 문제의 최적해는 작은 문제의 최적해를 기반으로 한다.

동적 프로그래밍의 접근 방법

1. 탑다운 접근 (Top-Down Approach):
   • 재귀적 해결: 문제를 재귀적으로 해결하면서 중복 계산을 방지하기 위해 결과를 저장한다.
   • 메모이제이션 (Memoization): 부분 문제의 결과를 저장하는 기술로, 이미 계산된 값을 재사용한다.
2. 바텀업 접근 (Bottom-Up Approach):
   • 반복적 해결: 가장 작은 부분 문제부터 해결하여 결과를 저장하고, 점점 큰 문제로 확장한다
   • 테이블화 (Tabulation): DP 테이블을 사용하여 모든 부분 문제의 결과를 저장하고 사용한다

---

장점:

중복 계산 방지	부분 문제의 결과를 저장하고 재사용하여 같은 문제를 여러 번 계산하지 않는다
다항 시간 복잡도	문제를 다항 시간 복잡도로 해결할 수 있는 경우가 많음. 예: 피보나치 수열 O(n)
정확한 최적해 보장	부분 문제의 최적해를 기반으로 전체 문제의 최적해를 보장한다
문제 구조 명확화	문제를 작은 부분 문제로 나누어 해결하므로 문제의 구조와 관계를 명확히 이해할 수 있다
효율적인 구현	메모이제이션(탑다운)과 테이블화(바텀업) 방법을 통해 효율적으로 문제를 해결할 수 있다

 

단점:

메모리 사용량 증가	부분 문제의 결과를 저장하기 위해 많은 메모리를 사용한다 문제의 크기와 부분 문제의 수에 따라 메모리 사용이 많아질 수 있다
문제의 구조에 제한적	중복 부분 문제와 최적 부분 구조를 가진 문제에만 적합하다 이러한 조건이 충족되지 않는 문제에서는 다른 알고리즘이 더 적합할 수 있다
구현 복잡성	문제의 상태와 전이 관계를 정확하게 정의해야 하므로 구현이 복잡할 수 있다
사전 계산 시간	모든 부분 문제를 해결해야 하므로 초기 계산에 시간이 소요될 수 있다