DP · Dynamic programming
동적 계획법
작은 답을 저장해 다음 답을 만들어요
이웃한 값을 함께 고르지 않고 최대 합을 구해요
지금 값을 안 고르면0
지금 값을 고르면0
저장한 최대 합0
현재 위치비교 대상확인한 값
예제 코드
C++
<vector> <algorithm>int non_adjacent_sum(const std::vector<int>& a) { std::vector<int> dp(a.size() + 1, 0); for (int i = 0; i < static_cast<int>(a.size()); ++i) { int skip = dp[i]; int take = dp[std::max(0, i - 1)] + a[i]; dp[i + 1] = std::max(skip, take); } return dp.back();}Python
def non_adjacent_sum(a): dp = [0] * (len(a) + 1) for i, value in enumerate(a): skip = dp[i] take = dp[max(0, i - 1)] + value dp[i + 1] = max(skip, take) return dp[-1]시작하기
작은 답부터 저장해요
아무것도 고르지 않으면 합은 0이에요. dp[0]에 0을 저장하고 앞에서부터 답을 만들어요.
사용 조건
이웃한 값을 함께 고르지 않으면서 최대 합을 구하는 예제예요. 앞부분에서 구한 답을 재사용해 전체의 답을 만들어요.
먼저 알아두면 좋아요
배열과 조건문, 최댓값 비교를 알고 시작해요. dp[i]는 앞 i개 원소에서 얻을 수 있는 최대 합이에요.
동작 원리
현재 값을 안 고르면 직전까지의 답을 그대로 사용해요. 고르면 바로 옆 원소를 건너뛰고 그 이전의 최대 합에 현재 값을 더해요.
두 후보 중 큰 값을 저장해요. 저장한 답을 다음 위치에서 다시 사용하므로 같은 앞부분을 여러 번 계산하지 않아요. 이 예제는 아무것도 고르지 않는 선택을 허용해요.
- 시간
- O(n) · 원소마다 두 후보를 비교해요
- 추가 공간
- O(n) · 앞부분별 최대 합을 저장해요
주의할 점
- dp의 각 칸이 무엇을 뜻하는지 먼저 정해요. dp[i]와 원래 배열 a[i]는 같은 종류의 값이 아니에요.
- 값 하나의 크기만 보고 선택하지 않아요. 지금까지의 최적 합을 비교해요.