dynamic programming
-
알고리즘, Dynamic ProgrammingData Structure & Algorithm 2024. 7. 8. 15:30
동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 이 기법은 하위 문제의 해를 재사용하여 전체 문제의 해를 구하는 데 사용됩니다. 동적 프로그래밍은 주로 최적화 문제를 해결하는 데 사용되며, 두 가지 중요한 속성을 가집니다: 최적 부분 구조(Optimal Substructure)와 중복 부분 문제(Overlapping Subproblems).동적 프로그래밍의 개념최적 부분 구조(Optimal Substructure):큰 문제의 최적 해가 그 부분 문제의 최적 해로부터 유도될 수 있는 속성을 의미합니다.예를 들어, 최단 경로 문제에서 전체 경로의 최적 해는 그 경로를 구성하는 부분 경로들의 최적 해로 구성될 수 있습..