[알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 이해하기

[ 목차 ]

1. 정의

  
2.재귀와의 차이점

 

3. DP를 사용할 수 있는 문제인지에 대한 판별

 

4. DP 사용 예시

 

5. 정리

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

• 동적 계획법이라고도 한다. (줄여서 DP)
• 복잡한 문제를 더 작은 하위 문제로 나누어 해결
• 알고리즘 자체가 아닌 알고리즘 설계기법 (그래서 동적 "계획법")

 

◈ 재귀(Recursion)와의 차이점

• 재귀는 대개 Top-Down 방식 
• DP는 대개 Bottom-Up 방식 (작은 문제들을 해결하며 큰 문제들로 다가감)
• DP는 Memoization 방식을 사용

※ Memoization

  -중복되는 계산 결과를 저장하는 메모리 기법 
   ex) 피보나치 수열 f(n) = f(n-1) + f(n-2)를 계산할때 메모이제이션을 사용하면  f(n-1)은 한번만 계산하고 저장해두어 계속

    호출하면 된다. (중복 계산을 줄여준다.)

 

 

 

◈DP를 사용 할 수 있는 문제인지에 대한 판별

1. 겹치는 부분 문제 (Overlapping Subproblems) 이어야 한다. 

• 작게 쪼개진 부분문제들의 결과값을 재활용하여 더 큰 문제를 풀어야하는데, 결과값들이 재활용되지 않는다면 겹치는 부분이 없어 문제를 해결하지 못한다.

2. 최적 부분 구조(Optimal Substructure) 이어야 한다. 

• 부분문제들의 결과값의 최선값이, 전체 문제의 최선값을 찾는데 영향을 주어야한다. 즉, 부분문제들의 최선값의 결과는 전체문제의 최선값이어야한다.

 

 

 

▶ DP 사용 방법

1. DP를 사용할수 있는 문제인지 판별
2. 변수 파악

3. 점화식 만들기

4. 메모이제이션

5. 베이스케이스 확인

6. 구현

 

이해를 돕기 위해, 백준의 9095번 문제 - 1, 2, 3 더하기를 예시로 들어보겠다.
https://www.acmicpc.net/problem/9095

1, 2, 3 더하기

 

 

 

---

 

 

 

1. DP를 사용할 수 있는 문제인지 판별

 

같은 숫자 하나를 가지고 1 ,2, 3의 갯수를 바꿔가며 더해보는 문제이기 때문에, 겹치는 문제(Overlapping Subproblems)라고 볼 수 있다.

 

2. 변수 파악

 

사실 이 문제에서 가장 어렵고 깨닫기 힘든 부분인데, 의외로 이 문제는 1의 개수, 2의 개수, 3의 개수가 변수가 아니다. 정수 n 이전의 정수 n-1, n-2, n-3의 방법의 수가 변수로 쓰인다. 그 이유는.....

 

3. 점화식 만들기

 

간단히 설명하면, n-1에 1을 더하고, n-2에 2를 더하고, n-3에 3을 더하면 n이 되기 때문에, 각각의 경우의 수들을 모두 더하면 n의 경우의 수가 된다는 원리이다. (이해하기 매우 어려움) 따라서 원리에 따라 세운 점화식은 아래와 같다.

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

 

 

4. 메모하기(Memoization )    a.k.a 반환하기

 

보통 dp라는 일차원 배열을 만들어, n개의 공간을 확보한 후, 각각의 경우의 수를 각 n번째 배열에 저장하는 방식으로 Memoization 을 구현한다. 위 문제의 경우. 정수 N의 입력 최댓값은 11이므로, 배열 크기는 12로 설정한다.

int *dp = (int *)malloc((12) * sizeof(int));

 

 

5. 베이스케이스 확인

 

이 문제에서 베이스 케이스는  정수 n이 1, 2, 3일 경우가 되겠다. 이 경우는 재귀적 리턴이 아닌 정수를 리턴해주어야 하는데 그 코드는 다음과 같다.

dp[1] = 1; 		// n = 1
if (n >= 2) dp[2] = 2; 	// n = 2
if (n >= 3) dp[3] = 4; 	// n = 3

 

 

 

6. 코드 구현 (C언어)

 

#include <stdio.h>
#include <stdio.h>

int f(int n) {
    // dp 배열 생성
    int *dp = (int *)malloc((12) * sizeof(int));
    
    // 초기값 설정
    dp[1] = 1; 			// n = 1
    if (n >= 2) dp[2] = 2; 	// n = 2
    if (n >= 3) dp[3] = 4; 	// n = 3

    // DP를 이용하여 값 계산
    for (int i = 4; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; // 점화식
    }
    int result = dp[n]; // n에 대한 결과 저장
    free(dp); // 동적 할당된 메모리 해제
    return result;
}

int main() {
    int t, n;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        scanf("%d", &n);
        printf("%d\n", f(n));
    }
    return 0;
}

 

 

 

 

▶출력 결과

 

 

맨처음 테스트 케이스입력 : 3

테스트케이스1  정수 입력 : 4 출력 : 7

테스트케이스2  정수 입력 : 7 출력 : 44

테스트케이스3  정수 입력 : 10 출력 : 274

 

입력과 동시에 출력되게 하였더니 cmd창이 조금 지저분하다 (...)

 

맞춤

▶정리

• DP는 알고리즘 설계기법
• DP는 Top-Down  Bottom-Up으로 모두 구현 가능
• 반복적인 작은문제로 나누어 해결하는 것과 Memoization이 핵심
• DP자체는 어렵지 않으나, 점화식 찾기, 베이스 케이스 찾기, 변수 파악 등의 실제적인 구현이 매우 어려움 (본인의 지적 수준에 따라 한계가 다름)