Dynamic Programming

뭔데 이게?
동적계획법(Dynamic Programming)은 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법이다.

언제 쓰지?

• 동일한 연산을 여러번 해야 할때, 단, 아래 조건에 부합해야 쓸 수있다.
  1) 큰 문제를 작은 문제로 나눌 수있다.
  2) 작은 문제에서 구한 정답은 항상 동일하다.

왜 쓰지?

• 동일 연산을 여러번 하지않고,딱! 한 번만 풀어서 불필요한 연산을 안하기 위함.

어떻게 쓰지?

• 저장해서 필요할때 꺼내쓴다. (= memoization 메모이제이션)
• 패턴. 즉, 점화식을 찾자.

1) 재귀호출

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){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(fibonacci(N));
    }
}

2) 반복문 : for

public class Fibonacci{ 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] dp = new int[N + 1];
        dp[1] = 1;
        for(int i = 2;i <= N;i++)
        	dp[i] = dp[i - 1] + dp[i - 2];
        System.out.println(dp[N]);
    }
}

쓰면 뭐가 달라지지?
ex) 중복된 문제를 한번만 풀다보니 계산량이 급진적으로 감소한다.

피보나치의 경우

기본 함수 호출 : O(2^n)
DP : O(n)

항상 좋은건가?

• 단점
  • 분할정복과 달리 조건에 부합하는 문제에만 쓸수있다.
  • 그리디알고리즘과 달리

출처:

• 위키백과: https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
• 인도남자의 DP https://youtu.be/5dRGRueKU3M
• 나동빈님의 DP https://blog.naver.com/ndb796/221233570962
• 전준엽님의 DP https://galid1.tistory.com/507?category=746457
• 낑깡님의 DP 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