← Back

동적계획법(DP) 개념 정리

동적계획법(DP, Dynamic Programming)은 같은 작은 문제가 반복해서 나올 때, 그 답을 저장해 한 번만 계산하는 기법이다.


DP를 사용할 수 있는 조건

알고리즘작은 문제로 나누기작은 문제 겹침답 저장
완전탐색(재귀)가능발생할 수 있음보통 하지 않음
분할정복O보통 독립적보통 필요 없음
DPOOO

DP를 적용할 때 확인할 조건은 두 가지다.

최댓값이나 최솟값을 구하는 문제뿐 아니라, 경우의 수를 세는 문제에도 작은 문제의 답을 조합하는 DP를 사용할 수 있다.

DP 풀이의 세 가지 요소

DP의 풀이는 상태 정의 → 점화식 → 초기 조건을 찾는 과정이다. 실제 구현은 재귀가 아닌 반복문으로도 할 수 있다.

단계뜻재귀 함수에서는
1. 상태 정의dp 한 칸의 의미파라미터 + 반환값
2. 점화식다른 상태의 답으로 현재 상태를 계산하는 규칙더 작은 문제를 호출하고 결과를 조합하는 부분
3. 초기 조건계산을 시작할 값종료 조건

표기 관례: 대문자 DP는 알고리즘 기법인 동적계획법을, 소문자 dp는 계산한 답을 저장하는 배열을 가리키는 데 흔히 쓴다.

상태 정의

상태 정의는 dp의 한 칸에 무엇을 적을지 정하는 일이다. 이걸 잘 정해야 앞의 칸들로 다음 칸을 계산하는 규칙, 즉 점화식을 세울 수 있다. 세 단계 중 가장 어렵지만, 상태만 잘 정하면 점화식과 초기 조건은 대부분 따라 나온다.

칸을 정할 때는 재귀 함수로 생각하면 쉽다. 함수에 넣는 값이 dp의 칸 번호가 되고, 함수의 결과는 그 칸에 적어 둔다. 그래서 f(i)의 결과는 dp[i]에, f(i, j)의 결과는 dp[i][j]에 들어간다.


코드 구현

// 메모이제이션 (memo는 -1로 초기화)
int f(int n) {
    if (n <= 2) return n;                  // 초기 조건
    if (memo[n] != -1) return memo[n];     // 저장된 답 재사용

    memo[n] = f(n - 1) + f(n - 2);         // 점화식

    return memo[n];
}

// 타뷸레이션
dp[1] = 1;
dp[2] = 2;                                 // 초기 조건
for (int i = 3; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];         // 점화식

시간복잡도는 같다. 타뷸레이션은 재귀 호출 비용이 없어 조금 더 빠르다.

← Back