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

  다이나믹 프로그래밍(Dynamic Programming)은 Divide and Conquer(분할정복) 기법과 같이 문제를 작은 부분 문제로 나누어 그 해를 결합해 문제를 해결하는 것이다. 어떤 문제를 점화식으로 표현할 수 있다면, 대부분 Dynamic Programming을 사용하여 문제를 해결할 수 있다.

 

다이나믹 프로그래밍(Dynamic Programming)

 

다이나믹 프로그래밍과 분할정복

 

  먼저 분할정복(Divide and Conquer)과 다이나믹 프로그래밍의 차이점을 알아보자. 분할정복의 경우 분할 문제들이 서로 겹치지 않는다. 각각의 다른 부분 문제를 해결하고 그 결과를 결합하는 것이다.

 

  다이나믹 프로그래밍은 부분 문제가 각각의 부분 문제를 가진다. 즉, 다이나믹 프로그래밍은 문제를 다음과 같이 점화식으로 표현할 수 있다는 것이다.

다이나믹 프로그래밍은 문제를 위와 같은 점화식으로 표현 할 수 있다.

  일반적으로 최적화 문제를 해결할 때, Dynamic Programming을 사용한다.

 

다이나믹 프로그래밍과 메모이제이션

 

  다이나믹 프로그래밍은 Top-down(하향식) 방식과 Bottom-up(상향식)으로 사용할 수 있다. Top-down 방식은 우리가 흔히 알고 있는 재귀함수를 이용하여 구현한다. 이때 Top-down 방식으로 재귀함수를 사용해 구현하면, 이미 계산해 도출한 값을 중복으로 계산하는 경우가 발생한다.

 

Top-down 방식으로 다이나믹 프로그래밍시 중복 문제가 발생한다.

  이런 경우 입력 값이 커지면 중복 계산을 하기 위한 메모리가 많이 발생하여, overflow가 발생할 수 있다. 메모리를 효율적으로 사용하기 위해서 Bottom-up 방식으로 작은 문제부터 해결하고, 작은 문제의 결과를 저장하여 큰 문제를 해결할 때 결과를 재사용해 메모리와 계산 속도를 개선한다. 이런 기술을 메모이제이션이라고 한다.(물론 Top-down방식에서도 메모이제이션 기술을 사용할 수 있지만, Bottom-up으로 접근하였을 때보다 구현이 복잡해질 가능성이 높다.)

 

 

피보나치수열을 통해 알아보는 다이나믹 프로그래밍

 

  다이나믹 프로그래밍을 사용해 해결할 수 있는 대표적인 문제는 피보나치수열이다. 먼저 재귀함수를 사용하여 Top-down 방식으로 피보나치수열 문제를 Java코드로 구현해 보았다.

public class Fibonacci {
    public static void main(String[] args) {

        System.out.println(fibonacci(10));
    }

    public static long fibonacci(int n){
        if(n == 1 || n == 2){
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

 

  두 번째로 Bottom-up 방식과 메모이제이션을 이용해 피보나치수열을 Java 코드로 구현해 보았다.

 

public class FibonacciUsingMemory {
    public static void main(String[] args) {

        System.out.println(fibonacciwithMemory(10));
    }

    public static long fibonacciwithMemory(int n){
        int[] fibonacci = new int[n + 1];

        if(n > 2){
            fibonacci[1] = 1;
            fibonacci[2] = 1;
        } else {
            return 1;
        }

        for(int i = 3; i < n + 1; i++){
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
        }

        return fibonacci[n];
    }
}