DP

동적계획법(DP)

• 상향식 접근
• 최하위 해답을 구하고, 해당 결과값을 이용해 상위 문제 해결
• Memoization 기법 사용 (이전 계산값 저장하는 기법)
• 문제를 쪼갤 때, 부분 문제 중복(재활용)  (ex> 피보나치 수열)

분할 정복 (divide & conquer) 

• 하향식 접근
• 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답 구함
• 재귀함수로 구현
• 문제를 쪼갤 때, 부분 문제 중복 X (ex> 병합 정렬, 퀵 정렬)
• Memoization 기법 사용 X