DP) Dynamic Programming

optimization problen

• 문제를 해결하는 최적의 답
• maximum, minimum을 구하는 문제

=> 가장 빨리 도착하는 경로의 소요 시간?, 주식을 사고 팔 때 가장 높은 수익?

---

 

다이나믹 프로그래밍

• 큰 문제를 작은 문제로 나눠서 푸는 방법
• 큰 문제를 작은 문제를 여러 번 재사용한다는 특징을 이용함
• 이전의 작은 문제의 값을 기억하고 같은 문제가 나오면 저장해둔 결과를 가져옴

다이나믹 프로그래밍 2가지 조건

• 최적 부분 구조(Optimal Substructure): 작은 문제들의 해결 방법을 합치면 큰 문제
  • 단, subproblems이 독립적이어야 함
• 중복되는 부분(Overlapping Subproblems): 문제를 작은 문제로 나누었을 때, 동일한 문제가 반복적으로 발생하는 경우 

 

다이나믹 프로그래밍 2가지 방식

 

	Top-Down Approach	Bottom-Up Approach
구조	recursive	iterative
결과 저장	memoization	tabulation
사용 시기	subproblems의 일부분으로 최적해를 구할 수 있을 때	모든 결과를 계산해야 최적해를 구할 수 있을 때

 

1. Top-Down Approach
   • 큰 문제를작은 문제로 나눔 (분할 정복)
   • 재괴 함수를 이용하여 구현
   • Memoization을 사용하여 결과 저장
2. Bottom-Up Approach
   1. 작은 문제부터 큰 문제를 해결
   2. 동적 계획법(Dynamic Programming)

---

다이나믹 프로그래밍 예시

1. recursive

public class Main {
    public static int fibonacci(int n) {
        if(n <= 1) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));  // 10번째 피보나치 수 출력
    }
}

 

2. Top-Down Approach

public class Main {
    public static Integer[] dp = new Integer[31];  // 메모이제이션을 위한 배열

    public static int fibonacci(int n) {
        if(n <= 1) {
            return dp[n] = n;
        } 
        if(dp[n] != null) {  // 이미 계산한 적 있는 문제라면 저장된 값 반환
            return dp[n];
        }
        return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);  // 계산 결과 저장
    }

    public static void main(String[] args) {
        dp[0] = 0;
        dp[1] = 1;
        System.out.println(fibonacci(10));  // 10번째 피보나치 수 출력
    }
}

 

3. Bottom-Up Approach

public class Main {
    public static int[] dp = new int[31];  // 결과 저장을 위한 배열

    public static void main(String[] args) {
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i <= 10; i++) {  // 작은 문제부터 차례대로 해결
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.println(dp[10]);  // 10번째 피보나치 수 출력
    }
}