[알고리즘 공부] 다이나믹 프로그래밍(DP, 동적 계획법)

다이나믹 프로그래밍(Dynamic Programming)

하나의 문제를 단 한번만 풀도록 하는 알고리즘

 

컴퓨터적인 사고력을 물어보기 적합해서 자주 출제되므로 확실하게 알아야 함. DP, 동적 계획법이라고도 함.

일반적으로 분할 정복 기법은 동일한 문제를 다시 푼다는 단점이 있음.
(정렬과 같은 몇몇 요소에 대해서는 동일 문제 다시 풀지 않음. 그래서 병합이나 퀵 정렬은 매우 빠름).

특히 피보나치 수열 같은 경우에는 단순 분할 정복으로 풀면 심각한 비효율성을 낳음.
(피보나치 수열 점화식: D[i] = D[i-1] + D[i-2])

재귀로 풀게 되면 동일한 데이터를 반복적으로 불필요하게 계산해야함. 이미 해결한 문제를 다시 반복적으로 해결하기 때문에 비효율적.

 

DP는 다음의 가정 하에 사용 가능

1. 큰 문제를 작은 문제로 나눌 수 있음
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일

 

즉, 크고 어려운 문제를 잘게 나누어서 해결한 뒤 나중에 전체의 답을 구함.

이미 계산한 결과는 배열에 저장해서 꺼내쓰는 메모이제이션(Memoization)이 사용된다는 점에서 분할정복과 다름.

 

#include <stdio.h>

int d[100];

int dp(int x) {
    if (x == 1) return 1;
    if (x == 2) return 1;
    return dp(x - 1) + dp(x - 2);
}

int main() {
    printf("%d", dp(30));
}

 

메모이제이션을 사용하지 않으면 2^50 만큼 연산을 해야함.
이는 약 1,000,000,000,000,000 번으로, 너무 많기 때문에 아무리 컴퓨터가 빠르게 연산하더라도 금방 출력하지 못함.

 

#include <stdio.h>

long long d[100];

long long dp(int x) {
    if (x == 1) return 1;
    if (x == 2) return 1;
    if (d[x] != 0) return d[x];
    return d[x] = dp(x - 1) + dp(x - 2);
}

int main() {
    printf("%lld", dp(50));	// 12586269025
}

 

메모이제이션 기법을 사용하면 시간복잡도가 O(N)으로 줄어듦. 계산하고 저장하기 때문에 높이인 N 수준만큼만 계산하면 되기 때문.
(50을 넣으면 int에서는 오버플로우 남)

 

DP 문제는 규칙성을 찾아 점화식을 세우는게 가장 중요.

예시 문제)

https://www.acmicpc.net/problem/11726

https://www.acmicpc.net/problem/11727