[TIL] 다이나믹 프로그래밍(Dynamic Programming, DP)

핵심 개념

복잡한 문제를 더 작고 간단한 하위 문제들로 나누어 해결하는 것 (=기억하며 풀기) 

1. 문제를 더 작은 하위 문제로 나눈다. 
2. 각 하위 문제의 해답을 계산하고 저장한다. 
3. 저장된 결과를 이용해 더 큰 문제의 해답을 구한다. 

특정한 알고리즘이 아니다. 그저 하나의 문제 해결 패러다임이다. 

 

주요 특징

1. 같은 하위 문제의 결과를 여러 번 계산하지 않고 저장된 결과를 재사용한다. 
2. 큰 문제의 최적해가 작은 문제들의 최적해로 구성된다. 

 

접근 방식

 

하향식(Top-down) : 메모이제이션 

• 큰 문제에서 시작하여 작은 문제로 나누어 해결한다.
• 재귀를 사용하지만, 계산된 결과를 저장(메모이제이션)하여 중복 계산을 방지한다.

상향식(Bottom-up) : 타뷸레이션 

• 가장 작은 부분 문제부터 시작하여 큰 문제를 해결한다. 
• 반복문을 사용하여 문제를 해결하며, 결과를 테이블에 저장한다. 

 

예제 

[백준] 동적 계획법 기초 문제

 

질문

1. 재귀와 반복문은 다이내믹 프로그래밍의 일종인가? 
   DP의 일종이 아니라 DP를 구현하는 데 사용할 수 있는 도구 중 하나이다. 
2.  Divide and Conquer와 Dynamic Programming의 차이는? 
   주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다. 차이점은 다이나믹 프로그래밍(DP)은 중복되는 부분 문제의 결과를 저장하고 재사용하여 계산 효율성을 높이는 방법이고, 분할 정복(Divide and Conquer)은 문제를 독립적인 작은 부분으로 나누어 각각 해결한 후 결과를 합치는 방법이다. (→부분 문제의 중복성)
   
   

참고 자료 

• https://hongjw1938.tistory.com/47