codeplus 백준 강사 강의 내용기반으로 정리한 내용입니다.(비공개 포스트)

다이나믹 프로그래밍

큰 문제를 작은 문제로 나눠서 푸는 알고리즘

분할정복도 위의 문제를 푸는 것이지만 작은 문제가 중복이 되어 작은문제를 이용해 큰 문제를 푸는 것이 다이나믹 프로그래밍

두가지 속성

1. Overlapping Subproblem - 부분문제가 겹침
2. Optimal Substructure - 최적 부분 구조(답이 항상 같은 결과)

DP

• 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야함
• Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같음
• 따라서, 정답을 한 번 구했으면 정답을 어딘가에 메모해놓음
• 이런 메모하는 것(Memoization)을 코드의 구현에서는 배열에 저장

다이나믹 프로그래밍 구현 방법

• Top-down(재귀)
• Bottom-up(for)