[백준/DP] 다이나믹 프로그래밍의 간단한 개념

 

 

1. Overlapping Subproblem

- 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.

- 문제를 작은 문제로 쪼갤 수 있다.

 

2. Optimal Substructure

- 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.

 

3. Dynamic Programming

- 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.

- 정답을 어딘가에 메모해놓는다. => Memoization

- 모든 문제를 풀어야 한다.

- 모든 문제는 1번만 플어야한다.

- 두 가지 구현방식

  1. Top-down : 큰 문제를 작은 문제로 나누어서 풀어간다(재귀)

  2. Botton-up : 가장 작은 문제를 통해서 큰 문제를 풀어간다(반복문)

 

 

4. 다이나민 문제 풀이 전략

1. 글로 점화식의 정의를 세운다.
2. 문제를 작게 만들 수 있는 방법을 찾는다.