3/27 DP(Dynamic Programming)
큰 문제를 작은 부분 문제로 나누어 해결 부분 문제의 결과를 저장하여 재사용 중복 계산을 제거하여 효율성 향상 피보나치 수열 [재귀 O(2^n)] -> [DP O(n)] 으로 극적인 성능 향상! 메모이제이션 - 계산 결과를 memo에 저장 - 같은 값
큰 문제를 작은 부분 문제로 나누어 해결
부분 문제의 결과를 저장하여 재사용
중복 계산을 제거하여 효율성 향상
피보나치 수열 [재귀 O(2^n)] -> [DP O(n)] 으로 극적인 성능 향상!
메모이제이션
- 계산 결과를 memo에 저장
- 같은 값을 다시 계산할 필요 없음
- 캐싱과 유사한 개념
DP가 필요한 경우
1. 최적 부분 구조: 부분 문제의 최적해로 전체 최적해 구성
2. 중복 부분 문제: 같은 문제가 반복적으로 등장
연속 해서 집을 털 수 없다.
dp 배열을 어떻게 정의 해야 할지가 중요하다
dp[n]= n번째까지 집을 털었을 경우 최대 금액
nums 에 각 집의 소지액을 나타내는 정수 배열이 주어졌다.
max( n번째 집을 선택했을 경우, n번째 집을 선택하지 않았을 경우 )
n번째 집을 선택했을 경우)연속된 n-1번째는 선택하지 못한다. -> nums[n] + dp[n-2]
n번째 집을 선택하지 않았을 경우)n-1번째까지의 최댓값이 된다.
dp[n]= max(dp[n-2] + nums[n], dp[n-1])