[Java]동적 계획법(Dynamic programming)

동적 계획법이란 미리 구해뒀던 답을 이용해 하나의 연산은 한 번만 하도록 하는 프로그래밍 패러다임이다.

지난 글에서 알아본 그리디 알고리즘이 그때그때 최적의 값을 찾아가는 방법이라면,

동적 계획법은 문제를 쪼개 모든 경우의 수를 살펴본 뒤 답을 구한다.

다만 연산 속도의 향상을 위해 이미 계산한 값을 저장해두는데, 이때 사용되는 메모리를 캐시(Cache)라고 한다.

동적 계획법이 적용될 수 있는 조건은 두 가지가 있는데,

• Overlapping Subproblem - 큰 문제를 중복되는 작은 문제로 나눌 수 있다.
• Optimal Substructure - 나눠진 작은 문제에서 구한 답을 이용해 전체 문제의 답을 구할 수 있다.

가 그것이다.

가장 쉬운 예로 피보나치수열을 들 수 있는데, 재귀 함수만을 이용한 구현은 메모리와 연산속도에 부담이 간다.

public static int fib(int n){

    if(n <= 1) return n;

    return fib(n - 2) + fib(n - 1);

    }

그 이유는 반복된 연산을 해야 하기 때문인데,

 

이는 위 그림과 같이 수열의 6번째 값만 구하는 데에도 지나치게 비효율적으로 동일한 연산이 반복해서 등장하기 때문이다.

구체적으로 위 문제는 O(2^n)의 시간 복잡도를 갖는다.

이 문제를 해결하는데 DP(Dynamic Programming)가 유용하게 쓰인다.

 

출처: https://thisdeveloperslife.com/post/1-0-3-problems

1.0.3 Problems

이러한 DP를 구현하는 방법은 크게 두 가지가 있는데,

• Top-down
• Bottom-up

순서대로 하나씩 살펴보자.

Top-down

Top-down 구현 방식은 전체 문제를 쪼개 가장 작은 문제에서 시작한 뒤, 작은 문제들의 답을 기억(Memoization)하고

재활용하여 문제를 해결해 나가는 방식이다. 문제를 쪼갠다는 점에서 재귀 함수를 주로 사용한다.

이 방식은 Bottom-up 방식에 비해 가독성이 좋지만 코드 작성이 어렵고 재귀 함수가 가진 단점을 어느 정도 공유한다.

private static long fib(int n) {
    long[] memo = new long[n + 1];
    
    if (n == 1 || n == 2) { // base case
        return memo[n] = 1;
    }
   
    if (memo[n] != 0) { // 기억된 값이 있을 경우 그대로 사용
        return memo[n];
    }
  
    else { // 재귀 함수 호출
        return memo[n] = fib(n - 1) + fib(n - 2);
    }
}

이 경우 시간 복잡도는 O(n)이다.

Bottom-up

Bottom-up 방식은 가장 작은 문제부터 순서대로 해결하며 표를 만드는(Tabulation) 과정을 거친 후

그 값을 읽어오는 방식이다.

 

fib(1)	fib(2)	fib(3)	fib(4)	fib(5)	fib(6)	fib(7)
1	1	2	3	5	8	13

구체적으로는 for문을 사용해 위와 같은 표를 작성한다고 생각하면 된다.

이 방식은 Top-down 방식에 비해 코드 작성이 쉽지만 가독성이 떨어진다는 단점이 있다.

private static long fib(int n) {

    long[] memo = new long[n + 1]; // 값을 저장할 배열을 만들어 초기화
    memo[1] = 1;
    memo[2] = 1;
    
    for(int i = 3; i <= n; i++) { // for문을 이용해 배열 채우기
        memo[i] = memo[i - 1] + memo[i - 2];
    }

    return memo[n];
}

이 경우에도 시간 복잡도는 똑같이 O(n)이다.