[알고리즘] Dynamic Programming(동적 계획법) 1. 다이나믹 프로그래밍이란? - "동적 계획법" - step1. 하나의 큰 문제를 여러 개의 작은 문제로 나눈다. - step2. 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다. - 하나의 문제 해결 패러다임 (특정한 알고리즘 X) - 기억하기 프로그래밍 2. 재귀와 DP의 차이? - 일반적인 재귀(Naive Recursion)를 단순히 사용 시, 동일한 작은 문제들이 여러 번 반복 > 비효율적 계산 ex. 피보나치 수열 - 재귀: f(n-1), f(n-2)에서 각 함수를 1번씩 호출 => 동일한 값을 2번씩 구하게 됨 => n 값이 증가함에 따라 호출되는 함수의 횟수는 기하급수적으로 증가 (약 7해) - DP: 한 번 구한 작은 문제의 결과 값을 저장하고 재사용 > 반복 X > 약 200회 .. 이전 1 다음
