알고리즘

(알고리즘) Dynamic Programming (동적 계획법)

✋ (알고리즘) Dynamic Programming (동적 계획법)이란? 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말입니다. 대표적으로 피보나치 수열을 구할 때 동적 계획법을 씁니다. 그러면 분할정복과 비슷하다는 말이 있을 텐데 아닙니다. 다릅니다. 📌 분할정복과의 다른점 결정적인 차이점이 있습니다. 바로 작은 문제가 중복이 일어나는지(동적계획법) 안일어나는지(분할정복기법) 입니다. 분할정복은 큰 문제를 해결하기 어려워 작은 문제로 나누는 알고리즘입니다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점입니다. 반면 동적계획법은 작은 부분문제들이 반복되는 것 (Result 값이 고정: F(0) =1, F(1) = 1) 을 이용해 풀어나가는 방법입니다. 즉, 분할정복과의 차이점은 작은 부분문제..