다이나믹 프로그래밍

sundays·2023년 2월 23일

algorithm

다이나믹 프로그래밍

큰 문제를 작은 문제로 나눠서 푸는 알고리즘
dynamic은 아무 의미가 없고 멋있어 보여서 사용하는 단어라고 한다
optimal substructure - 최적 부분 구조를 가진다
overlapping sub-problems - 겹치는 작은 부분 문제가 존재 한다

풀이 방법

문제에서 구하려고 하는 답을 문장으로 나타내본다
메모리제이션(memorization) 를 사용하여 문제를 푼다
문제를 작은 문제로 나누고 수식을 이용하여 문제를 표현하도록 한다

예시

피보나치

f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2) (n >= 2)

피보나치에서는 n번째 피보나치 수를 구하게 될때 n - 1과 n - 2 이 겹치는 작은 부분 문제가 존재하고 있다. 재귀를 사용하거나 n번까지 for loop로 값을 구할 수 있다

해결 방법

1. top-down

재귀(recursive) 를 사용해서 푼다

int fibonacci(int n) {
	if (n <= 1) {
    	return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

해당 재귀 코드를 개선을 하여 메모리제이션을 이용하게 되면 다음과 같습니다. 메모리제이션이란 같은 문제는 구할때마다 중복해서 계산하지 않기 위해 배열에 저장되는 것을 말합니다.

int[] dp = new int[n + 1];
int fibonacci(int n) {
	if (n <= 1) { 
    	return n;
    }
    if (dp[n] > 0) {
    	return dp[n];
    }
    return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

메모리제이션을 사용하여 dp[n]의 값을 검증하여 존재 여부를 확인하여 바로 리턴하면 됩니다. 이렇게 되면 모든 문제를 각 한번씩만 풀어서 함수의 시간복잡도가 줄어들게 됩니다.

2. bottom-up

문제를 크기가 작은 문제부터 차례대로 푼다
문제의 크기를 조금씩 크게 만들면서 문제를 푼다

int fibonacci(int n) {
	int[] dp = new int[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];
}