[java] Dynamic Programming(DP / 동적 계획법)

Dynamic Programming(DP / 동적계획법) 이란?

: 재귀 알고리즘에서 동일한 하위 문제를 여러번 계산하는 것을 방지하는데 사용하는 기술

한 번 계산했던 부분을 다시 계산하지 않아서 속도가 빠르다는 특징이 있다.

 

---

동적 계획법 예제   [피보나치 수열]

*피보나치 수열이란 ? 각 숫자가 앞의 두 수의 합인 수열

(ex. 0,1,1,2,3 일때)

n = 항의 수
1. n <= 1이라면, 1을 반환
2. 그렇지 않다면, 앞의 두 숫자의 합을 반환

5항까지의 피보나치 수열을 계산한다고 했을 때,
첫번째 항은 0, 두번째 항은 1, 세번째 항은 0(첫번째 항)과 1(두번째 항)의 합인 1
네번째 항은 1(두번째 항)과 1(세번째 항)의 합인 2
다섯번째 항은 1(세번째 항)과 2(네번째 항)의 합인 3

여기서는 아래와 같이 이전 단계의 결과를 사용한 것을 확인할 수 있다.
F(0) = 0
F(1) = 1
F(2) = F(0) + F(1)
F(3) = F(1) + F(2)
F(4) = F(2) + F(3)

이것을 동적 계획법 접근 방식이라고 한다.

---

동적 계획법의 종류(타뷸레이션(Tabulation) / 메모이제이션(Memoization))

 

1. 타뷸레이션(Tabulation) - Botton up 방식(상향식 접근방법 / 모두 계산하면서 차례대로 진행)

답을 구하기 위한 모든 계산을 Table 방식으로 저장하는 for문 방식

public class Main {
    public static int fib(int n){ // 피보나치 수열 일반 풀이(계산했던 부분도 다시 계산)
        if (n <= 1){ // n이 0이거나 1인경우
            return n; // n값을 그대로 돌려줌
        } else { // 그게 아니라면
            return fib(n - 1) + fib(n - 2); // 재귀호출
        }
    }

    public static int Tabulation(int n){ // 타뷸레이션 방식 풀이
        int[] dp = new int[n < 2 ? 2 : n + 1]; // DP용 메모리
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) { // Tabulation은 기본적으로 for문을 이용(아래쪽부터 채워주는 Bottom-up 방식)
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String args[]){
        // testcode
        System.out.println(fib(7)); // 값 : 13
        System.out.println(Tabulation(7)); // 값 : 13
    }
}

 

 

2. 메모이제이션(Memoization) - Top down 방식(하향식 접근방법 / 계산이 필요한 순간 계산하며 진행)

중복되는 계산은 한 번만 계산하는 재귀 방식

public class Main {
    public static int fib(int n){ // 피보나치 수열 일반 풀이(계산했던 부분도 다시 계산)
        if (n <= 1){ // n이 0이거나 1인경우
            return n; // n값을 그대로 돌려줌
        } else { // 그게 아니라면
            return fib(n - 1) + fib(n - 2); // 재귀호출
        }
    }

    static int[] dp = new int[8];
    public static int Memoization(int n){ // 메모이제이션 방식 풀이

        if (n <= 2){
            return 1;
        }
        if (dp[n] != 0){ // 이미 계산을 해서 값이 들어가 있을 때
            return dp[n];
        }
        dp[n] = Memoization(n - 1) + Memoization(n - 2); // 값이 안들어가있을 때(계산한적이 없을때) 재귀호출 형태로 호출하며 계산, 기록
        return dp[n];
    }
    public static void main(String args[]){
        // testcode
        System.out.println(fib(7)); // 값 : 13
        System.out.println(Memoization(7)); // 값 : 13
    }
}

 

DP활용 문제는 코딩테스트 / 기본 문제 풀이등에 많이 사용되니 개념을 정확히 익혀놓자.

---

DP활용 문제

[백준] 문제번호 1463 (1로 만들기)(java) (tistory.com)