Dynamic Programming

Dynamic Programming이란?

DP(Dynamic Programming)는 문제를 서브 문제들로 나누고 문제와 서브 문제의 관계를 토대로 답을 구하는 문제 해결 기법입니다.

분할 정복과 유사하지만 분할 정복과 달리 DP는 분할된 서브 문제들의 해가 다른 서브 문제에서 사용될 수 있습니다. 따라서 서브 문제들의 해를 테이블에 저장하여 다시 계산하지 않도록 합니다.

즉, DP는 속도를 위해 메모리를 희생하는 문제 해결 기법입니다.

구현

DP를 구현하는 방법은 Recursive 방식과 Iterative 방식으로 나뉩니다. Recursive 방식은 큰 문제에서 작은 서브 문제들을 재귀적으로 호출하여 문제를 해결하는 Top-down 방식입니다. Iterative 방식은 작은 서브 문제들부터 해결하여 큰 문제에 도달하는 Bottom-up 방식입니다.

Fibonacci Number

Fibonacci Number

피보나치 수는 첫째 항과 둘째 항이 1이고 나머지 항들은 바로 앞 두 항의 합인 수열을 말합니다. 0을 0번째 항에 두기도 합니다.

구현

Recursive 구현

int Fibonacci(int n) {
    if (n == 0)
    	return 0;
    else if (n == 1)
        return 1;
    else
    	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Iterative 구현

int Fibonacci(int n) {
    int prev = 0, now = 1;
    
    if (n == 0)
    	return 0;
    else if (n == 1)
        return 1;
    else {
    	for (int i = 2; i <= n; i++) {
            int next = now + pre;
            pre = now;
            now = next;
        }
        return now;
    }
}