[알고리즘] 다이나믹 프로그래밍(Dynamic Programming)

  다이나믹 프로그래밍(Dynamic Programming)이란, 계산된 결과를 기록하고 재활용하여 문제의 답을 구하는 알고리즘입니다. 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서 중간 계산 결과를 기록하기 위한 메모리를 필요로 합니다. 한 번 계산한 부분을 다시 계산하지 않아도 돼서 속도가 빠르다는 장점이 있습니다. 동적 계획법이라고도 불립니다.

  다이나믹 프로그래밍에는 타뷸레이션(Tabulation)과 메모이제이션(Memoization) 두 가지 방법이 있습니다. 먼저 타뷸레이션은 하위 문제부터 풀면서 올라가는 상향식 접근 방법으로, 모두 계산하면서 차례대로 진행합니다. 반대로 메모이제이션은 큰 문제에서 하위 문제를 확인해가며 진행하는 하향식 접근 방법으로, 계산이 필요한 순간 계산하면서 진행합니다.

  이 알고리즘의 대표적인 예로는 피보나치 수열 풀이가 있습니다. 타뷸레이션을 이용한 방법은 이미 풀이한 적이 있으므로 이번에는 메모이제이션을 이용한 풀이만 진행해보도록 하겠습니다.

 

  타뷸레이션 구현 코드(피보나치 수열)

  [프로그래머스 코딩테스트] 피보나치 수(Java) https://sigfriede.tistory.com/127 

  

  메모이제이션 구현 코드(피보나치 수열)

public class FibonacciMemoization {
    public static int fibonacci(int n) {
        int[] memo = new int[n + 1];
        return fib(n, memo);
    }
    private static int fib(int n, int[] memo) {
        if (n <= 2) {
        	return 1;
        }
        if (memo[n] != 0) {
        	return memo[n];
        }
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }
}

  매개 변수 n을 받는 fibonacci 메소드를 생성합니다.

  배열 memo의 크기를 n + 1로 지정합니다.

  fib 메소드를 호출하고 인자에 n과 memo를 넣어 반환합니다.

  첫 번째 if문에서 n이 2보다 크면 1을 반환합니다.

  두 번째 if문에서 memo의 n 번째 원소가 0이 아니라면 memo의 n 번째 원소를 반환합니다. memo의 n 번째 원소가 0이 아니라는 것은 이미 앞서 계산했다는 뜻이기 때문입니다.

  만약 앞선 조건에 해당하지 않는다면 memo의 n 번째 원소에 fib 메소드를 호출하여 n - 1과 n - 2를 인자로 받아 더합니다. memo의 n 번째 원소에 값을 저장한 후 반환합니다.

 

  타뷸레이션과 메모이제이션 방법은 모두 별도의 데이터 저장 메모리를 필요로 한다는 공통점이 있습니다. 그러나 타뷸레이션은 반복문을 이용해서, 메모이제이션은 재귀 함수를 이용해서 풀이한다는 차이점이 있습니다.