[Algorithm] Dynamic Programming

동적 프로그래밍이란?

문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘

문제 풀이 순서

1. 문제가 원하는 정답을 찾기 위해 가장 먼저 완전 탐색(Brute-Force Search) 접근을 시도한다.
2. 근데, 완전 탐색 과정에서 탐색하게 되는 경우가 지나치게 많아서 도저히 안 될 것 같다.
3. 이럴 때, 모든 경우를 빠르게 탐색하는 방법으로 동적 프로그래밍 접근을 시도한다.

동적 프로그래밍 접근 순서

1. 풀고 싶은 가짜 문제 정의
2. 가짜 문제를 풀면 진짜 문제를 풀 수 있는가?
3. 초기값은 어떻게 되는가?
4. 점화식 구해내기
5. 진짜 문제 정답 출력하기

예제

피보나치 수열

• 가짜 문제 정의
  • D[i] : i 번째 까지 피보나치 수열의 합.
• 진짜 문제를 풀 수 있는가?
  • 피보나치 수열 A[1...N]에서 부분 수열의 합.
  • D[i]의 값이 구하고자 하는 부분 수열의 합.
• 초기값은 어떻게 되는가?
  • D[0] : 0
  • D[1] : 1
• 점화식 구해내기
  • D[i] = D[i-1] + D[i-2]
• 진짜 문제 정답 출력하기

List<Integer> list = new ArrayList<>(); // D[i] 값을 저장하기 위한 배열
// 초기값 D[0] == 0, D[1] == 1 저장
list.add(0, 0);
list.add(1, 1);

// 점화식 D[i] = D[i-1] + D[i-2] 이용하여 D[N]까지 계산
for (int i = 2; i <= n; i++) {
    list.add(i, list.get(i - 1) + list.get(i - 2));
}

return list.get(n);