DP(다이나믹프로그래밍)

분할정복 기법 + 메모이제이션으로 푸는 알고리즘

 

작은 문제들을 풀다보면 같은 문제들을 반복해서 풀 수 있고, 그 문제들은 매번 재계산 하는것이 아닌 따로 값을 저장해 두었다가 재사용하는 기법.

 

예를들어 피보나치 수열을 들 수 있다.

피보나치 수열

위와 같은 점화식의 피보나치 수열은 n이 1보다 클 경우 자신의 이전 항 들의 값으로 이루어짐.

 

f(5)를 구하기 위해선

f(5) = f(4) + f(3)

f(4) = f(3) + f(2)

f(3) = f(2) + f(1)

f(2) = 1

f(1) = 0

 

위 처럼

f(1) = 2

f(2) = 3

f(3) = 3

f(4) = 2

f(5) = 1

 

위처럼 중복해서 계산이 필요하고 이는 숫자가 커질수록 더 많은 연산을 필요로하며 '지수 시간 시간복잡도'를 발생

정해진 시간안에 문제해결이 안된다.

 

이럴 때 메모이제이션 기법을 사용하여 이미 구했던 f(3),f(4)... 등의 숫자를 저장해놓으면 한번만 호출되므로 시간은 O(N)의 시간만 필요하게 됨.

 

이처럼 DP는 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푸는 알고리즘.

분할 정복과 비슷한데 가장 큰 차이는 겹치는 문제의 발생유무, 이로인한 메모이제이션 기법필요 이다.