Dynamic Programming, DP
분할정복과 비슷한 개념이긴하지만 memoization(이전 결과값의 저장과 활용)이 추가된 알고리즘을 말한다.
분할정복기법은 큰 문제를 반으로 나누어 잘게 쪼개고, 분할된 문제를 풀면서(혹은 정렬하면서) 큰 문제를 해결하는 과정을 의미하였다.
다만 분할정복의 단점은 분할된 문제들을 푸는 단계(step, 일련의 과정)들마다 동일한 해결기법을 계속 적용해야한다는 점이다.
이는 기존 완전이진트리에 정렬이 잘 된 data에 한해서는 빠르게 문제를 풀 수 있지만, 반복적으로 동일한 값을 사용하게되는 경우(*피보나치수열)엔 급속도로 성능이 저하된다.
동적계획법을 적용할 수 있는 가장 직관적인 형태는 점화식으로 표현되어, 기존에 도출하였던 결과값을 이후에 다시 이용하는 경우이다.
위와 같은 피보나치수열 점화식이 있다고 가정해보자.
이를 분할정복(완전이진트리 구성)으로 해결한다고 했을때, 위와 같이 불필요한 데이터 중복과 공간낭비가 발생하여 성능저하를 일으키는 요인이 발생한다.
이때 동적계획법, 특히 memoization을 이용하면 N이 커져도 시간복잡도를 2^n에서 n으로 매우 효율적으로 줄일 수 있다.
이전의 값들을 별도 배열에 저장하는 기법을 의미한다.
D(N)의 값은 미리 저장된 D(N-1), D(N-2) 값을 이용하여 도출한다.
이 방법이 분할정복과 DP와 다른 점이고, 이 관점이 컴퓨터적인 사고를 검증하는데 적합하기 때문에 DP관련한 문제종류가 매우 많고 활용이 많이 된다.
첫번째, 두번째는 초기값을 미리 지정해주어야 한다.
#피보나치수열
#DP의 가장 대표적인 예시
result = [0] * 100
def dp(n):
if n == 1:
return 1
elif n == 2:
return 1
else:
result[n] = dp(n-1) + dp(n-2)
return result[n]
print(dp(30))