- [알고리즘] 동적 프로그래밍 방법2025년 03월 15일
- Song hyun
- 작성자
- 2025.03.15.오후07:00
728x90반응형[알고리즘] 동적 프로그래밍 방법
-알고리즘의 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.
1. 동적 프로그래밍 방법(Dynamic Programming)
-동적 프로그래밍 방법은 입력의 크기가 가장 작은 부분 문제부터 해를 구해 저장해두고, 이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적으로 만드는 상향식 접근 방법이다.
-작은 문제들은 서로 독립일 필요가 없다.
-따라서 한 번 사용한 작은 문제의 해가 다음에 또 사용될 수도 있다.
-욕심쟁이 방법과 마찬가지로 최솟값/최댓값을 찾는 최적화 문제에 주로 사용된다.
-> 플로이드 알고리즘 역시 동적 프로그래밍이 적용된 알고리즘!
728x90반응형'알고리즘' 카테고리의 다른 글
[알고리즘] 점근성능 (0) 2025.03.17 [알고리즘] 알고리즘 분석 (0) 2025.03.16 [알고리즘] 분할정복 방법 (0) 2025.03.15 [알고리즘] 욕심쟁이 방법 (0) 2025.03.14 [알고리즘] 알고리즘 설계 (0) 2025.03.13 다음글이전글이전 글이 없습니다.댓글
스킨 업데이트 안내
현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)