[DP] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)

---

1. 동적 계획법

2. 구현 방법(피보나치 예제)

---

1. 동적 계획법

하나의 큰 문제를 큰 문제를 작은 문제로 나누어 해결하고 그 결과를 저장하여 중복 계산을 피하는 하나의 방법론입니다.

동적 계획법을 활용하는 대표 문제로는 피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제, 최단 경로, 동전 거스름돈 문제 등이 있습니다.

 

DP(Dynamic Programming) 문제를 만났을 때는 부분 문제를 활용할 수 있는지, 중복 계산을 줄일 수 있는지 2가지 사항을 고민하여 적용하면 됩니다. 해당 포스팅에서는 피보나치 수열으로 구현해보겠습니다.

 

2. 구현 방법(피보나치 예제)

- Bottom-Up 방식(반복문)

아래(가장 작은 상태)에서부터 위(큰 상태)로 계산을 수행하는 방식입니다.

 

int fib(int n) {
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

 

점화식을 사용해서 dp[i]를 계산합니다.

 

i	dp[i] 값	설명
0	0	0 (초기값)
1	1	1 (초기값)
2	1	dp[2] = 1 + 0 = 1
3	2	dp[3] = 1 + 1 = 2
4	3	dp[4] = 2 + 1 = 3
5	5	dp[5] = 3 + 2 = 5

 

위와 같은 방식으로 작은 값부터 차례대로 채워나가기 때문에 중복 계산을 방지합니다.

 

- Top-Down 방식(메모이제이션)

위(가장 큰 상태)에서부터 아래(작은 상태)로 계산을 수행하는 방식입니다.

한 번 계산한 결과를 저장하여 중복 호출을 줄입니다.

 

int fib(int n) {
    if (n <= 1) return n;
    if (dp[n] != 0) return dp[n];
    return dp[n] = fib(n - 1) + fib(n - 2);
}

 

if (n <= 1) return n; fib(0), fib(1)은 고정된 값이 존재하기 때문에 그대로 반환해줍니다.

if (dp[n] != 0) return dp[n]; 처음에 dp 배열을 모두 0으로 초기화했기 때문에 값이 들어가지 않은 배열의 값은 0일 것입니다. 만약 값이 들어갔다면 이미 계산된 값이므로 재귀 호출없이 반환합니다.

return dp[n] = fib(n - 1) + fib(n - 2); 재귀적으로 호출하여 dp[n]에 저장합니다.

 

DP는 막상 문제를 보면 구현하기 쉽지 않더라구요..

꾸준히 문제를 풀고 학습하겠습니다.

---

참고 사이트

알고리즘 - Dynamic Programming(동적 계획법)

 

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3