알고리즘 - Dynamic Programming(동적 계획법)

▶ 다이나믹 프로그래밍

- 복잡한 큰 문제를 간단한 여러 작은 문제로 나눠서 푸는 알고리즘

 

▶ 다이나믹 프로그래밍 방법.

- 모든 작은 문제들은 한번만 풀어야 함.

- 작은 문제들에 대한 정답을 어딘가에 메모해 놓아야 함 -> Memoization

- 같은 문제가 나타나면 메모해 두었던 작은 문제의 결과값을 이용함.

- 피보나치 수열 사용< fn(n) = fn(n-1) + fn(n-2) + ... +fn(0) >

 

▶ 다이나믹 프로그래밍 조건

1. 작은 문제가 반복이 일어나는 경우.

2. 최적 부분 구조. 작은 문제의 결과 구할 때 과정에 사용된 정답 항상 같음.

 

▶ 다이나믹 프로그래밍 구현 방법

1. Top-Down : 재귀함수 이용한 방법(문제를 여러 문제로 나눠 놓고 필요할 때 구함)

2. Bottom-Up : 작은 문제부터 풀고, 조금씩 크게 만들며 문제 푸는 방법(문제를 여러 문제로 나누고 풀어 놓음)

3. 점화식 세워야 함!

- 점화식 세우기 : 크기가 작은 문제들 위주로 시작해 문제 크기 점점 키우면서 풀어나갈 수 있도록!

4. 초기값 설정해주어야 함.