[알고리즘] 동적 프로그래밍 방법

[알고리즘] 동적 프로그래밍 방법

 

-알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.

 

 

1. 동적 프로그래밍 방법(Dynamic Programming)

-동적 프로그래밍 방법은 입력의 크기가 가장 작은 부분 문제부터 해를 구해 저장해두고, 이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적으로 만드는 상향식 접근 방법이다.

-작은 문제들은 서로 독립일 필요가 없다.

-따라서 한 번 사용한 작은 문제의 해가 다음에 또 사용될 수도 있다.

-욕심쟁이 방법과 마찬가지로 최솟값/최댓값을 찾는 최적화 문제에 주로 사용된다.

 

-> 플로이드 알고리즘 역시 동적 프로그래밍이 적용된 알고리즘!