DP는 중복되는 부분 문제를 한 번만 계산해 저장합니다. 재귀에 memoization을 붙이는 top-down 방식과 작은 상태부터 채우는 bottom-up 방식이 있습니다. 핵심은 상태 정의와 점화식을 정확히 세우는 것입니다.
꼬리질문
조금 더 깊게 물어본다면
답변 뒤에 이어질 수 있는 질문들을 하나씩 열어볼 수 있어요.
DP 상태 정의가 중요한 이유는?
상태가 문제의 부분 답을 정확히 표현해야 점화식이 성립합니다. 상태를 잘못 잡으면 중복 계산을 줄여도 답이 틀립니다.
최적 부분 구조란?
큰 문제의 최적해가 작은 부분 문제들의 최적해로 구성되는 성질입니다. 예를 들어 최단 경로 문제에서 A에서 C까지의 최단 경로는 A에서 B, B에서 C까지의 최단 경로를 포함합니다. 이 성질이 없으면 DP를 적용해도 올바른 답을 보장할 수 없습니다.
중복 부분 문제란?
동일한 부분 문제가 여러 번 반복해서 등장하는 성질입니다. 피보나치 수를 단순 재귀로 계산하면 f(3)이 여러 경로에서 중복 계산되는 것이 대표적인 예입니다. 이 성질이 없으면 메모이제이션을 해도 이득이 없습니다.
Memoization vs tabulation?
Memoization은 필요한 상태를 재귀적으로 계산하며 저장하는 top-down 방식이고, tabulation은 작은 상태부터 순서대로 채우는 bottom-up 방식입니다.
시간복잡도는 어떻게 계산하나요?
대체로 상태 개수와 각 상태를 계산하는 비용을 곱해 계산합니다. 예를 들어 n개 상태를 O(1)에 계산하면 O(n)입니다.
공간 최적화는 언제 가능한가요?
현재 상태가 가까운 이전 상태 몇 개에만 의존한다면 전체 테이블 대신 일부 값만 유지할 수 있습니다.
Greedy vs DP 구분 방법은?
Greedy는 현재의 최선 선택이 전체 최선으로 이어진다는 증명이 필요합니다. 그런 보장이 약하고 여러 선택 결과를 비교해야 하면 DP를 의심합니다.
분할 정복과 DP의 차이는?
두 방법 모두 문제를 작은 부분 문제로 나눕니다. 차이는 부분 문제가 겹치는지 여부입니다. 분할 정복은 부분 문제들이 서로 독립적이라 결과를 저장할 필요가 없습니다. 병합 정렬이 대표적인 예입니다. DP는 같은 부분 문제가 반복해서 등장하고 그 결과를 재사용해 효율을 얻습니다.
부가 설명
피보나치 수를 재귀로 그대로 풀면 같은 값을 계속 다시 계산합니다. f(5)를 구할 때 f(3)이 여러 번 등장하는 식입니다. DP는 이런 반복을 발견하고, 한 번 구한 결과를 저장해 다음 계산에서 재사용합니다.
하지만 모든 최적화 문제가 DP가 되는 것은 아닙니다. 큰 문제의 답이 작은 문제의 답으로 구성되는 optimal substructure가 있어야 하고, 같은 상태가 여러 번 등장해야 이득이 있습니다. DP의 핵심은 배열 자체가 아니라 상태가 무엇을 의미하고, 이전 상태에서 현재 상태로 어떻게 넘어오는지입니다.