동적 프로그래밍 -> 기억하기 프로그래밍
하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 함
DP의 사용 조건
1) Overlapping subproblems
동일한 작은 문제들이 반복하여 나타나는 경우
2) Optimal substructure
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우
부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있다.
DP는 특정한 경우에 사용하는 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰일 수 있다.
DP 사용
1) DP로 풀 수 있는 문제인지 확인
2) 문제의 변수 파악
e.g., 피보나치수열(f(n))에서 n
3) 변수 간 관계식 만들기 (점화식)
e.g., f(n) = f(n-1) + f(n-2)
4) 메모하기 (memoization)
변수의 값에 따른 결과를 저장/ 변수의 개수에 따라 배열의 차원 달라짐
5) 기저 상태 파악하기
가장 작은 문제의 상태를 알아야함
6) 구현하기
- Bottom-Up (Tabulation 방식) -> 반복문 사용
- Top-Down (Memoization 방식) -> 재귀 사용
구현 방법
1) Bottom-Up 방식
아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식
do[0]이 기저 상태, dp[n]이 목표 상태 -> dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식
2) Top-Down 방식
dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
