반응형 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 다음 반응형
