[알고리즘 이론] 12. DP (동적 계획법)

DP (Dynamic Programming)

• 큰 문제를 작은 문제들로 나누어 푸는 알고리즘이다.

DP의 조건

1. 작은 문제의 반복이 일어나는 경우
2. 같은 문제는 구할 때마다 정답이 같다.

1. Memoization 을 이용한 피보나치 수열 알고리즘

• 반복하면서 구한 정답은 또 구하지 않게 저장하면서 작은 문제로 나누어 푸는 알고리즘.

public class Fibonacci {
    static int[] dp = new int [1000];
    static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if(dp[n] != 0) return dp[n];
        dp[n] = fibonacci(n - 2) + fibonacci(n - 1);
        return dp[n];
    }

    public static void main(String[] args) {
        fibonacci(n);
    }
}

2. 반복문을 이용한 피보나치 수열 알고리즘

public class Fibonacci {
    public static void main(String[] args) {
        int[] dp new int[n + 1];
        dp[1] = 1;
        for(int i = 2; i <= n; i++) 
            di[i] = dp[i - 1] + dp[i - 1];
         int result = dp[n];   
    }
}

탑다운, 바텀업

1. 탑다운 (재귀 호출 사용)

• 가장 먼저 호출하는 문제는 가장 큰 문제 이기 때문에 이런 명칭이 붙음
• 장점은 가독성이 좋고, 본래 점화식을 이해하기 쉽다.

2. 바텀업 (반복문 사용)

• 가장 작은 문제들부터 차례차례 답을 쌓아 올려가기 때문에 이런 명칭이 붙음
• 장점은 함수를 별개로 부르지 않아 시간과 메모리를 소량 더 절약할 수 있다는 점이 있다.

알고리즘 문제 추천

1. 피보나치 수 2 (브론즈 1)

• https://www.acmicpc.net/problem/2748

2. 1로 만들기 (실버 3)

• https://www.acmicpc.net/problem/1463

3. 가장 긴 감소하는 부분 수열 (실버 2)

• https://www.acmicpc.net/problem/11722

4. LCS 2 (골드 4)

• https://www.acmicpc.net/problem/9252

참고 자료

https://velog.io/@sanizzang00/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-Dynamic-Programming%EB%8F%99%EC%A0%81-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D