알고리즘
[알고리즘] 동적 프로그래밍 방법
Song hyun
2025. 3. 15. 19:00
728x90
반응형
[알고리즘] 동적 프로그래밍 방법
-알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.
1. 동적 프로그래밍 방법(Dynamic Programming)
-동적 프로그래밍 방법은 입력의 크기가 가장 작은 부분 문제부터 해를 구해 저장해두고, 이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적으로 만드는 상향식 접근 방법이다.
-작은 문제들은 서로 독립일 필요가 없다.
-따라서 한 번 사용한 작은 문제의 해가 다음에 또 사용될 수도 있다.
-욕심쟁이 방법과 마찬가지로 최솟값/최댓값을 찾는 최적화 문제에 주로 사용된다.
-> 플로이드 알고리즘 역시 동적 프로그래밍이 적용된 알고리즘!
728x90
반응형