동적 계획법(Dynamic Programming, DP)
동적 계획법이란? 동적 계획법(DP, 다이내믹 프로그래밍)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해 두고 재활용한다가 핵심이다. 동적 계획법 사용 이유 일반적인 재귀(Native Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 피보나치수열은 아래와 같다. 1, 1, 2, 3, 5, 6, 13, 21, 34, 55, 89, 144... 피..
2023. 9. 1.
