[기초] 다이나믹 프로그래밍

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

- Dynamic 이라는 것은 아무 의미가 없다.

다이나믹 프로그래밍은 두 가지 속성을 만족해야만 이렇게 풀 수 있다.

1. 겹치는 작은 문제 Overlapping subproblem

2. 최적 부분구조

 

겹치는 작은 문제?

피보나치 수를 예로 들어보자.

$$ F_N = F_(N-1) + F(N-2) $$

가 나온다. 

 

Optimal Substructure?

-문제의 정답을 작은 문제의 정답에서 구할 수 있다.

Optimal Substructure 를 만족하려면, 같은 문제는 구할 때마다 정답이 같다.

그러므로, 어떤 작은 문제의 정답을 구했으면 이 정답을 저장해둔다. Memoization!

재귀를 사용하여 호출하다보면 분명 중복되어 나타나는 같은 문제가 있기 때문에 메모이제이션을 활용하면 큰 계산 절약을 이끌어낼 수 있다.

 

1. 모든 문제를 풀어야 함.

2. 모든 문제는 한 번만 풀려야 함.

 

다이나믹 프로그래밍을 구현하는 방식 2 가지

1. Top-down (재귀)

- 큰 문제를 작은 문제로 나누어서 푸는 것. 가장 작은 문제에서 return 하여 최종적으로 큰 문제를 품

2. Bottom-up (반복문)

- 작은 문제부터 풀어서 큰 문제를 푸는 법.

 

다이나믹 프로그래밍 을 구현하는 법

1. 점화식의 정의를 세우는 것.

2. 문제를 작게 만들 수 있는 방법 찾기 

( N 번째 피보나치 수는 N-1 번째와 N-2 번째를 더해서 만든다. -> 문제를 작게 만듦. -> 점화식의 정의 -> top down 이나 bottom up 으로 푼다. 둘 중 시간 복잡도는 같기 때문에 편한 것을 사용한다.)