반응형 Tabulation1 [Coding Test][Python] Dynamic Programming(DP) 개념 및 예제 ※ Dynamic Programming(DP, 동적 프로그래밍) 란?DP는 큰 문제를 작은 문제로 나누고, 작은 문제의 결과를 재사용하여 큰 문제를 해결하는 알고리즘이다. 즉, 동일한 하위 문제가 반복되는 문제에서 효율적이다. DP 주요 개념Optimal Substructure(최적 부분 구조)문제를 작은 하위 문제들로 나눌 수 있으며, 하위 문제의 최적 해를 사용하여 전체 문제의 최적 해를 구할 수 있어야한다.ex) 피보나치 수열 : F(n)=F(n−1)+F(n−2)Overlapping Subproblems(중복 부분 문제)동일한 하위 문제가 여러번 반복해서 나타나는 경우, 이를 저장해 재사용하면 계산량을 줄일 수 있다.ex) 피보나치 수열의 F(5)를 계산할 때 F(4),F(3)을.. 2025. 1. 27. 이전 1 다음 반응형
