DP(동적 계획법)

큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정

계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식

 

분할정복  vs DP

분할 정복은 부분 문제가 중복되지 않아서 DP와 다름 DP는 부분문제가 중복되어 재활용한다.

 

그리디 vs DP

그리디 알고리즘은 순간의 최선을 구하지만 DP는 모든 경우에 수에서 최적해를 구함

 

DP의 방법

상향식 접근 (타뷸레이션)

작은 하위 문제부터 풀면서 올라감

모두 계산하면서 차례대로 진행

 

하양식 접근 (메모이제이션)

큰문제에서 하위문제를 확인해가며 진행

계싼이 필요한 순간 계산하며 진행