Dynamic programming이란?

Dynamic programming이란 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘으로, 중복 계산을 피하기 위해 실행 중간중간의 결과를 저장하고 이를 재사용하는 방식입니다. 어떠한 큰 문제를 작은 하위 문제로 분할하여 큰 문제의 최적 해결 방법을 하위 문제의 최적 해결 방법을 조합하여 만들어냅니다. 

 

피보나치 수열을 예로 들어보겠습니다.

public static int fibo(int x) {
	if(x == 1 || x == 2) {
		return 1;
	}
    return fibo(x - 1) + fibo(x - 2);
}

fibo(6)을 생각해봅시다. fibo(6)은 fibo(5)와 fibo(4)를 호출하고 fibo(5)는 fibo(4)와 fibo(3)을, fibo(4)는 fibo(3)과 fibo(2)를 호출합니다. 이때 fibo(5)가 호출한 fibo(4)는 fibo(3)과 fibo(2)를 또 호출하게 됩니다. 이때 fibo(3)이나 fibo(2)와 같이 반복적으로 호출되는 것을 볼 수 있는데, 여기서 x 값이 더욱 커지면 반복해서 호출되는 것은 훨씬 많아질 것입니다.

 

이러한 문제는 Dynamic programming을 사용하면 효율적으로 해결할 수 있습니다. 다만 아래 조건을 만족할 때 Dynamic programming이 사용 가능합니다.

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

피보나치 수열은 이러한 조건을 만족하는 대표적인 문제입니다. 

 

 

 

📝메모제이션 기법이란?

메모이제이션(Memoization)은 Dynamic programming을 구현하는 방법 중 하나로, 계산한 결과를 메모리에 저장하여 동일한 계산이 필요한 경우 이전에 계산한 값을 재사용하는 기법입니다. 즉, 값을 저장하는 방법으로 캐싱(Caching)이라고도 합니다.

 

메모제이션을 구현하는 방법은 한 번 구한 정보를 리스트에 저장하기만 하면 됩니다. Dynamic programming을 재귀적으로 수행하다가 같은 정보가 필요하면 이미 구한 정잡을 리스트에서 그대로 가져오면 됩니다. 

public class FibonacciMemoization {
    // 계산된 결과를 저장할 배열
    static int[] memo;

    public static int fibo(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }

        // 이미 계산한 값이 있으면 바로 반환
        if (memo[x] != 0) {
            return memo[x];
        }

        // 아직 계산한 적 없는 경우, 피보나치 값을 계산하고 메모에 저장
        memo[x] = fibo(x - 1) + fibo(x - 2);
        return memo[x];
    }

    public static void main(String[] args) {
        int n = 10;
        memo = new int[n + 1];

        int result = fibo(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

 

 

Top-Down 방식⬇️ &  Bottom-up 방식⬆️

Top-Down 방식은 재귀적으로 문제를 해결하면서 중간 결과를 저장하고 나중에 재사용하는 방식으로, 큰 문제를 해결하기 위해 작은 문제를 호출합니다. 이는 재귀 함수를 사용하여, 메모리 상에 적재되는 일련의 과정을 따라야 하기 때문에 오버헤드가 발생할 수도 있습니다. (메모제이션은 이 Top-Down 방식에 국한되어 사용되는 표현이라는 것을 기억합시다.) 

 

Bottom-Up 방식은 하위 문제부터 시작하여 큰 문제로 진행하며, 중간 결과를 테이블에 저장하는 방식입니다. 이때 이 테이블을 DP 테이블이라고 하며 결과 저장용 리스트라고 생각하시면 됩니다. 주로 반복문을 사용하여 모든 하위 문제에 대한 결과를 한 번에 계산하고 저장하기 때문에 메모리 사용량이 더 효율적입니다. 

 

따라서 Dynamic programming을 구현할 때 입력 크기가 크거나 성능이 중요한 경우에는 Bottom-Up 방식이 유용할 수 있습니다.