[JAVA] 다이나믹 프로그래밍(DP) 이론

DP?
하나의 문제는 딱 한번만 풀 수 있도록 하는 알고리즘

기본적으로 상당수의 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고있다
대표적인 예로 피보나치 수열이 있는데 피보나치 수열은 x번째 답을 구하기 위해 x-1과 x-2를 1이 될때까지 구하는 수열이다
점화식 D[x] = D[x-1] + D[x-2]
위 공식에 따라 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...이라는 순으로 나타나게 된다

 과정을 그려보면 위 그림과 같이 나온다.
그림에서도 볼 수있 듯이 15를 찾기 위해 14와 13을 분할하고 14에서도 다시 13을 확인하는 것을 알 수 있다
그래서 풀이의 시간복잡도는 2^n을 가지고 있는 것을 알 수가 있고 n이 커질 수록 기하급수적으로 수가 커지는 문제가 발생한다

이를 해결하기 위해 사용하는 알고리즘이 DP이다
코드로 구현해보자

public int fibonacci(int x){
    if(x == 1) return 1;
    if(x == 2) return 1;
    return fibonacci(x-1) + fibonacci(x-2);
}

재귀함수만 사용하여 구현한 피보나치 수열이다
만약 50번째 수열의 값을 구하고 싶어서 이 코드를 실행할 경우 1천조번이 넘는 연산이 필요하다

이를 해결하기 위해 DP를 어떻게 적용해야할까?
답은 이미 한번 했던 연산을 저장하는 Memoization을 사용하면 된다
예를 들어 그림과 같이 15번째를 구할 때 14와 13을 탐색하게되는데 간단하게 14와 13의 탐색 값을 저장하면 된다
코드로 구현해보면 이렇게된다

int[] save = new int[100001];
public int fibonacci(int x){
    if(x == 1) return 1;
    if(x == 2) return 1;
    if(save[x] != 0) return save[x];
    return save[x] = fibonacci(x-1) + fibonacci(x-2);
}

 탐색을 진행하면서 배열의 값이 저장된적이 없다면 값을 저장하고 저장한적이 있다면 저장된 값을 반환해주면된다

이러한 과정으로 풀게되면 2^n이였던 시간복잡도는 n으로 풀 수 있게 된다