[C++] DP(Dynamic Programming) 동적 계획법

< 큰 문제를 작은 문제로 나눠서 푸는 알고리즘의 종류 2개 > 1) Dynamic Programming (DP) - 큰 문제들을 나누었을 때, 작은 문제들이 중복될 수 있다. - 따라서 중복을 효율적으로 처리하는 방법을 파악하는 것이, 문제로 발생함 2) 분할정복 (Divde & Counqer) - 큰 문제들을 나누었을 때, 작은 문제들이 중복될 수 없다.

<정의>

- 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고 다시 그 결과를 이용하여 큰 문제를 해결 할 때 사용하는 방식으로 프로그래밍 기법 중 하나이다.

- 피보나치 수열로 문제를 풀면 시간초과가 나기 때문에 배열에 미리 저장하고 답이 필요할 때마다 반환하는 방식이다.

  ex) 피보나치 수열 5번을 구하는 문제 -> for문 5번 or 한번 피보나치를 최대치까지 돌려서 배열에 저장하고 반환

 

<조건>

1. Overlapping Subproblem : 겹치는 작은 문제들

2. Optimal Substructure : 최적부분구조 (문제의 정답을, 작은 문제의 정답들을 통해 구할 수 있는 구조)