[알고리즘] 동적계획법(Dynamic Programing)

1. 동적 계획법이란

알고리즘 기법 중 하나로, 주어진 문제를 부분 문제로 잘게 쪼개어 해결함으로써, 궁극적으로 최종 문제를 해결하는 방법

 

2. 동적 계획법 사용 조건

• 문제를 부분문제로 나눌 수 있을 때
• 부분 문제들로 최종 문제를 풀 수 있을 때

3. 동적 계획법 예시

동적 계획법

위 그림에서 보듯이 F(1) , F(0)을 구하여 최종 F(5)까지 구하여 최종답을 제시 한다.

대표 예제) 피보나치

 

4. 주요 특징

• 주로 점화식을 이용하여 푸는 경우가 많다
• 계산한 값을 메모리에 저장하기 때문에 속도는 빨라도 공간을 많이 차지할 수 있다.
• 동적 계획법 계산할 때 채우는 배열을 동적 테이블이라 함(Dynamic table)