다이나믹 프로그래밍(동적 계획법)

💡다이나믹 프로그래밍이란?

메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법으로, 이미 계산될 결과(작은 문제)는 별도의 메모리 영역에 저장하여(메모이제이션) 다시 계산하지 않도록 한다. Divde and Conquer(분할정복)과 다른 점은, 분할 정복의 경우 중복되는 문제가 발생하지 않으나, DP의 경우 중복되는 문제가 발생한다.

 

 

 

 

💡다이나믹 프로그래밍의 조건

• 최적 구분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결 가능하다.
• 중복되는 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.

 

 

💡탑다운, 바텀업

다이나믹 프로그래밍 구현은 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성된다.

탑다운의 경우, 재귀 호출을 사용하며, 이때 가장 먼저 호출되는 문제는 가장 큰 문제이기 때문에 이런 명칭이 붙었다. 탑다운 방식은 가독성이 좋고, 본래 점화식을 이해하기 쉽다.

바텀업의 경우, 반복문을 사용하며, 가장 작은 문제들부터 차례대로 답을 쌓아 올리기 때문에 이렇게 불린다. 바텀업의 장점은 함수를 별개로 부르지 않아 시간과 메모리를 소량 더 절약할 수 있다는 점이다.

 

 

 

 

💡예제 코드

전에 포스팅했던 피보나치 수열의 메모이제이션을 이용한 풀이도 다이나믹 프로그래밍을 사용하는 예시이다.

 

문제1) 철수는 편의점에서 일을하는데, 하는 일 중 하나가 물건 값을 계산하고 거스름돈을 거슬러주는 일이다. 만약 거스름돈 5원을 거슬러줘야 하는데 동전이 1원, 2원, 5원짜리가 무한히 있다고 가정해보자. 그러면 철수는 다음과 같은 경우의 수(4가지)로 거스름돈을 거슬러줄 수 있다.

• 5원 1개
• 2원 2개 + 1원 1개
• 2원 1개 + 1원 3개
• 1원 5개

이렇게 동전의 종류와 거스름돈을 매개변수로 받아 거슬러 줄 수 있는 모든 경우의 수를 리턴하는 프로그램을 작성해라.

• 동전의 종류 : int[] type
• 거스름돈 : int target

풀이)

우선 위의 예제를 좀 더 간단히  쪼개어 보자.

int[] type= {1,2,5} / 0원을 만드는 경우 : 1로 설정

 

1원만으로)

1원을 만들 때(target=1) : 1

2원을 만들 때 : 1+1 

3원을 만들 때 : 1+1+1

4원을 만들 때 : 1+1+1+1

5원을 만들 때 : 1+1+1+1+1

 

1원과 2원만으로)

1원을 만들 때 : 1

2원을 만들 때 : 1+1 , 2 (기존의 1원으로 2원을 만드는 경우의 수 + 0원(2-2)을 만드는 경우의 수)

3원을 만들 때 : 1+1+1 , 1+2 (기존의 1원으로 3원을 만드는 경우의 수 + 1원(3-2)을 만드는 경우의 수)

4원을 만들 때 : 1+1+1+1 , 1+1+2,  2+2 (기존의 1원으로 4원을 만드는 경우의 수 + 2원(4-2)을 만드는 경우의 수)

5원을 만들 때 : 1+1+1+1+1 , 1+1+1+2, 1+2+2 (기존의 1원으로 5원을 만드는 경우의 수 + 3원(5-2)을 만드는 경우의 수)

 

1원과 2원과 5원으로)

1원을 만들 때 : 1

2원을 만들 때 : 1+1 , 2 (그대로)

3원을 만들 때 : 1+1+1 , 1+2 (그대로)

4원을 만들 때 : 1+1+1+1 , 1+1+2,  2+2 (그대로)

5원을 만들 때 : 1+1+1+1+1 , 1+1+1+2, 1+2+2 , 5 (기존의 1원으로 5원을 만드는 경우의 수 + 0원(5-5)을 만드는 경우의 수)

 

코드)

public long ocean(int target, int[] type){
    long[] dp = new long[target + 1];
    dp[0] = 1;

    for(int i=0;i<type.length;i++){
        for(int j=1;j<=target;j++){
            if(type[i]<=j)
                dp[j] += dp[j - type[i]];
        }
    }
    return dp[target];
}

 

 

 

 

 

문제2) 철수는 편의점에서 일을하는데, 하는 일 중 하나가 물건 값을 계산하고 거스름돈을 거슬러주는 일이다. 만약 거스름돈 14원을 거슬러줘야 하는데 동전이 1원, 4원, 5원,6원짜리가 무한히 있다고 가정해보자. 그러면 철수가 거스름돈을 줄 수 있는 경우의 수 중에서 동전을 갯수를 최소로 할 때의 갯수는 어떻게 되는가?

 

풀이)

가장 화폐 단위가 큰 것부터 사용한다고 동전을 최소로 사용함을 보장할 수 있는가? NO

6원*2 + 1원 *2 -> 4개

5원*2 + 4원*1 -> 3개 ( 사용하는 동전의 갯수가 더 작음)

 

이러한 경우는 위에서 했던 것 처럼 1원만 사용할때, 1원과 4원을 사용할 때, 1원, 4원, 5원을 사용할 때, 모두 사용할때로 나눠서 풀어야 한다. 그렇게 정리하면 아래와 같다.

 

 

그리고 1원만 사용할때에서 1원,4원만 사용할때로 넘어갈 때 갯수를 비교해 더 적은 것을 저장하도록 해줘야 한다.

1원,4원 -> 1원, 4원, 5원으로 넘어갈 때도 마찬가지.

 

위의 문제는 거스름돈을 낼 수 있는 모든 경우의 수를 구해야 하지만, 이 문제의 경우 동전을 최소로 사용할때를 구해야 하므로, 매번 어느 것이 최소인지 체크해줘야 한다.

 

코드는 아래와 같다.

 

코드)

public void coin(int[] coins, int target){
    int[] dp = new int[target + 1];
    for(int i=1;i<=target;i++) dp[i]=1000001;

    for(int i=0;i<coins.length;i++){
        System.out.printf("동전 %d 사용시\n", coins[i]);
        for(int j=coins[i];j<=target;j++){
            dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            System.out.printf("%d %d\n",j,dp[j]);
        }
        System.out.println("-".repeat(60));
    }
    System.out.println(dp[target]);
}