Overlapping-Subproblems

중복되는 하위 문제(Overlapping Subproblems) 동적 계획법(Dynamic Programming)은 복잡한 문제를 더 작고 간단한 하위 문제로 나누어 해결하는 알고리즘 패러다임이다. 동적 계획법이 효과적으로 적용되기 위해서는 두 가지 핵심 특성이 필요하다: 최적 부분 구조(Optimal Substructure) 중복되는 하위 문제(Overlapping Subproblems) 이다. 중복되는 하위 문제(Overlapping Subproblems)의 기본 개념 중복되는 하위 문제는 동일한 하위 문제가 알고리즘 실행 과정에서 여러 번 반복해서 나타나는 특성을 말한다. 즉, 문제를 해결하는 과정에서 같은 계산이 여러 번 수행되는 경우이다. 중복되는 하위 문제가 있을 때 동적 계획법은 각 하위 문제의 결과를 저장(메모이제이션)하여 중복 계산을 피함으로써 효율성을 크게 향상시킨다. ...