Dynamic Programming

17 Dec 2021

algorithm

다이나믹 프로그래밍

메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.
대표적인 방법이 다이나믹 프로그래밍 기법으로 동적 게획법이라고 표현하기도 한다.

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다.

n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
단 1번째, 2번째 피보나치 수 = 1

위 식을 프로그래밍으로 표현하려면 재귀 함수를 사용할 수 있다.

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

그러나 fibo(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문에 심각한 문제가 생길 수 있다.
호출되는 함수를 생각해보면 동일한 함수가 반복적으로 호촐되는 것을 알 수 있다.

이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.
다만 항상 사용할 수는 없고 다음 조건을 만족할 때 사용할 수 있다.

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

이 문제를 메모제이션 기법을 사용해 해결할 수 있다.
한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.

d = [0] * 100 

def fibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]
    
print(fibo(99))

다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

탑다운(top-down) & 보텀업(bottom-up) 방식

탑다운 방식(메모제이션): 재귀 함수를 이용해 큰 문제를 해결하기 위해 작은 문제를 호출하는 것
보텀업 방식: 반복문을 이용해 작은 문제를 차근차근 답을 도출하는 것

문제: 1로 만들기

점화식: min(Ai-1, Ai/2, Ai/3, Ai/5) + 1
1을 더해주는 이유는 함수의 호출 횟수를 구해야 하기 때문이다.
1을 빼는 연산을 제외하고 해당 수로 나누어떨어질 때만 더 작은 수를 비교하면 된다.

풀이 코드

private static void solution(int x) {
	int[] dp = new int[x + 1];
	
	for (int i = 2; i < x + 1; ++i) {
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0) {
			dp[i] = Math.min(dp[i], dp[i / 2] + 1);
		}
		if (i % 3 == 0) {
			dp[i] = Math.min(dp[i], dp[i / 3] + 1);
		}
		if (i % 5 == 0) {
			dp[i] = Math.min(dp[i], dp[i / 5] + 1);
		}
	}

	System.out.println(dp[x]);
}

문제: 개미 전사

i번째 식량창고에 대해서 털지 안털지의 여부를 결정할 때, 2가지 경우만 비교하면 된다.

(1) i-1번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 없다.
(2) i-2번째 식량창고를 텅ㅇ기로 결정한 경우 현재의 식량창고를 털 수 있다.

한 칸 이상 떨어진 식량창고는 항상 털 수 있기 때문에 i-3번째 이하의 식량창고에 대해서는 고려할 필요가 없다.

더 많은 식량을 털 수 있는 경우를 선택하면 된다.

dp[i] = Math.max(dp[i-1], dp[i-2]+arr[i]);

풀이 코드

d[0] = arr[0];
d[1] = Math.max(arr[0], arr[1]);
for (int i = 2; i < n; ++i) {
    d[i] = Math.max(d[i - 1], d[i - 2] + arr[i]);
}

System.out.println(d[n - 1]);

문제: 바닥 공사

풀이 코드

d[1] = 1;
d[2] = 3;

for (int i = 3; i <= n; ++i) {
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796;
}

System.out.println(d[n]);

문제: 효율적인 화폐 구성

화폐 단위가 큰 단위가 작은 단위의 배수가 아니기 때문에
매번 가장 큰 화폐 단위로부터 처리하는 방법으로는 해결할 수 없고 다이나믹 프로그래밍을 이용해야 한다.

금액 i를 만들 수 있는 최소한의 화폐 개수를 ai, 화폐의 단위를 k라고 했을 때
(ai-k는 금액 i-k를 만들 수 있는 최소한의 화폐 개수를 의미)

ai-k를 만드는 방법이 존재하는 경우, ai = min(ai, ai-k + 1)
ai-k를 만드는 방법이 존재하지 않는 경우, ai = 10001

풀이 코드

private static void solution(int n, int m, int[] coin) {
    int[] dp = new int[m + 1];
	Arrays.fill(dp, 10001);

	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = coin[i]; j <= m; j++) {
			if (dp[j - coin[i]] != 10001) {
				dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1);
			}
			System.out.println(Arrays.toString(dp));
		}
	}

	if (dp[m] == 10001) { 
		System.out.println(-1);
	} else {
		System.out.println(dp[m]);
	}
}