DP(다이나믹 프로그래밍) 알고리즘

DP란?

한줄로 정리하면

이전 값의 결과를 저장해서 다음 결과 값을 이전 결과값의 값을 사용하여 불필요한 계산을 줄이는 것이다.

 

말로 설명하면 참 애매한 말인데 가장 쉽게 이해할 수 있는 것은 피보나치 수열이다.

피보나치 수열은 처음 1,1로 시작하여 그 다음 수는 그 이전의 두 개의 수의 합으로 결정되기 때문에 이것을 n까지의 입력을 받아 n순서의 피보나치 코드로 구현해보면

n = int(input())
result = [0]*n
a = 0
b = 1
result[0] = a
result[1] = b
for i in range(2,n):
    result[i] = result[i-2] + result[i-1]
print(result[-1])

처음값과 두번쨰 값을 저장해 두면 3번째 부터는 자동으로 뒤의 값을 활용하여 구할 수 있게 만들어졌다.

따라서 이러한 문제를 만났을 때에는 일일히 경우의 수를 다 따르기보다는 문제의 패턴을 파악하고, 그에 대한 점화식을 찾는다면 생각보다 문제는 쉽게 풀 수 있을 것이다.