[Algorithm] 다이나믹 프로그래밍(Dynamic programming)

다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘

• 분할 정복 기법은 '정렬'과 같은 몇몇 요소에 대해 동일한 문제를 다시 푼다는 단점을 가지고 있음.
• 단순 분할 정복으로 풀면 심각한 비효율을 낳는 대표적인 예시로 피보나치 수열이 있음
  • 피보나치 수열의 점화식
    • D[i] = D[i - 1] + D[i -2]
    • 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 
    • 이런 경우 병합 정렬처럼 단순 분할 정복 기법을 사용하는 경우 이미 해결한 문제를 다시 반복적으로 해결하여 비효율적임
  • 다이나믹 프로그래밍 가정
    • 1번 가정
      • 큰 문제를 작은 문제로 나눌 수 있음
    • 2번 가정
      • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일함
    • 크고 어려운 문제가 있다면 먼저 잘게 나누고 해결하여서 나중에 전체의 답을 구하는 것
    • Memorization
      • 이미 계산한 결과는 배열에 저장하여 나중에 동일한 계산을 해야할 때 저장된 값을 단순히 반복하면 됨
      • 아래 코드에서 d 배열에 값들을 저장

public class DynamicProgramming {
	
	static int d[] = new int[100];
	
	public static int dp (int x) {
		if(x == 1) return 1;
		if(x == 2) return 1;
		if(d[x] != 0) return d[x];
		return d[x] = dp(x - 1) + dp(x - 2);

	}

	
	public static void main(String[] args) {
		System.out.println(DynamicProgramming.dp(50));
	}

}