동적 계획법(Dynamic Programming, DP)

재귀를 이용하여 코딩테스트를 하던도중 계속해서 실행시간 초과로 실패하였는데 알고보니 DP라는 것을 이용해야 하는 문제 였다.

 

 

동적 계획법 (DP)

최소의 단위로 문제를 쪼개어 연산한 뒤 배열에 저장하고 그 값들을 계속해서 이용하여 연산 후 배열에 저장, 결국엔  최종 값까지 도달하는 알고리즘 설계 기법이다.

 

간단히 말해 최소 단위의 문제를 푼뒤 그 값들을 계속해서 재활용하여 최후의 값을 구하는 방식이다. 

 

 

DP의 특징

DP를 사용할때 문제를 최소단위에서부터 연산을 시작하여 나온 값을 이용해 연속적으로 연산을 하게되는데 이는 재귀 구조와 매우 비슷하다.

 

이렇게  답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야 하는 종류의 문제의 구조를 최적 부분 구조(OPtimal Substructure)라 부르며 DP는 이런 문제에서 재귀에 비해 훨씬 효율이 좋은 시간복잡도를 가지고 있다. 

 

하지만 DP의 경우 배열에 현재까지 연산을 완료한 모든 값들을 저장해주기때문에 재귀를 사용하는것보다 공간복잡도에서 효율이 좋지 않다.

 

동적 계획법의 대표적인 방식으로는 Top-down과 Bottom-up이 있다.

 

 

예시 - 피보나치수열 

 

재귀

int fibonacciRecursion(int target){
    if(target<=1) return target;
    return fibonacciRecursion(target-1) + fibonacciRecursion(target-2);
}

피보나치수열을 재귀를 이용하여 풀게되면 그림에서와 같이 피보나치수열의 5번째 값을 구하기 위해서 15번의 재귀함수를 호출해야 한다. 또한 이 과정에서 동일한 함수들이 반복적으로 호출되게 된다.

• fib(0) : 3번
• fib(1) : 5번
• fib(2) : 3번
• fib(3) : 2번

DP와 재귀의 차이점은 위와 같이 반복적으로 같은연산을 하는 값들을 배열에 저장하여 사용한다는 점이다.

 

 

DP - Bottom up

int fibonacciDp(int target) {
    int[] table = new int[target+1];//원하는 수열값 +1 만큼의 배열 생성
    table[0] = 1; //문제의 최소단위에서 연산을 위해 사용될 값을 0번인덱스에 저장

    for(int i=2; i<table.length; i++){
        table[i] = table[i-1] + table[i-2];
    }// 반복문을 통해 0번수열부터 원하는 수열까지 연산

    return table[target];
    // 이후 배열에 저장된 입력된 n번째 수열을 반환
}

// 입력값 5, 결과 5
// 배열 table = [1, 0, 1, 1, 2, 3, 5]

Bottom-up의 경우 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것이다. 첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 풀면 세 번째 피보나치 수를 구하는 식으로 n번째 피보나치 수를 구한다.

 

(Top-down의 경우 밑의 동적계획법 참조)

 

참조

나무위키 참조

동적계획법 : https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95 

백트래킹 : https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9 

 

블로그 참조

동적계획법 : https://hongjw1938.tistory.com/47