동적 계획법 (Dynamic Programming, DP)
큰 문제를 작은 문제로 나누어 풀고, 중복 계산을 줄여 효율적으로 해결하는 알고리즘 기법🚀 동적 계획법(DP)이란?✅ 큰 문제를 작은 하위 문제로 나누어 푸는 방식✅ 이전에 계산한 결과를 저장하여 중복 계산을 줄임 → 메모이제이션(Memoization) 사용 / 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가 ✅ "최적 부분 구조(Optimal Substructure)"와 "중복되는 부분 문제(Overlapping Subproblems)"가 존재할 때 사용 가능 🚀 DP의 두 가지 접근 방법1️⃣ Top-Down (재귀 + 메모이제이션)큰 문제를 작은 문제로 나누어 푸는 방식재귀 + 딕셔너리(memo) 또는 리스트(dp[])를 사용하여 중복 계산을 줄임def fib(n): if n..
Python/코딩테스트
2025. 3. 9. 17:04