목록2025/02/28 (1)

데이터 분석 기술 블로그

동적 계획법(DP, Dynamic Programming)

동적 계획법 DP"복잡한 문제를 작은 부분 문제로 나누어 해결하고, 중복 계산을 줄여 효율적으로 최적해를 찾는 알고리즘 기법"한 번 계산한 값을 저장(Memoization)하여 중복 계산 방지부분 문제를 조합하여 전체 문제의 해답을 구하는 방식피보나치수열, 최단 경로, 배낭 문제 등 다양한 문제에서 활용동적 계획법(DP) 동작 원리문제를 작은 부분 문제(Subproblem)로 나눔각 부분 문제를 해결하면서 결과를 저장(Memoization or Tabulation)저장된 결과를 이용하여 최종 문제를 해결# Pseudo Code_Top-DownFUNCTION Fibonacci(n): IF n 동적 계획법(DP)의 일반적인 시간복잡도탑다운(Top-Down) 방식: O(부분 문제 개수 × 각 문제 풀이 ..
데이터 사이언스/알고리즘 2025. 2. 28. 19:38
이전 Prev 1 Next 다음