[알고리즘] Dynamic Programming (동적 계획법)
Dynamic Programming (동적 계획법)이란? 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것입니다. DP는 왜 사용하는 걸까? 피보나치 수열을 예시로 들 수 있습니다. 피보나치 수열은 아래와 같습니다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... => fibo(n) = fibo(n-1) + fibo(n-2) 이런 알고리즘에서 f(n)을 호출한다고 하면 아래와 같이 중복되는 숫자들이 늘어나게 됩니다. 즉, 시간복잡도가 O(2^n)이 걸리게 됩니다. 하지만 이미 계산했던 값들을 저장한다면 O(n)까지 줄일 수 있습니다. 이것이 DP를 사용하는 이유입니다. DP의 접근방식 기본적..
2023. 2. 12.
