[알고리즘] DP? 다이나믹 프로그래밍

DP란 다이나믹 프로그래밍(Dynamic Programming) 또는 동적 계획법이라고 불리는 알고리즘이다.

큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 해결할 때 사용한다.

저장? 한 번 계산한 문제는 다시 계산하지 않도록

 

예시로 피보나치 수열을 들 수 있다.

피보나치 수

의 점화식은

f(n) = f(n-1) + f(n-2)

 f(n-1)와 f(n-2)를 각각 따로 구하게 되면 f(n-2) 만큼 중복된 계산이 있을 것이다.

그래서  f(n-2)까지의 계산 결과를 저장한 후  f(n-1)를 구하기 위해  f(n-2), f(n-3)을 꺼내 계산하고

최종적으로 f(n)을 구하기 위해  f(n-1), f(n-2)을 꺼내 계산하는 것

 

 

DP는 2가지 방식으로 구현할 수 있다.

 

Bottom-Up (반복문)

DP의 전형적인 형태는 바텀업(Bottom-Up) 방식으로 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있는 장점이 있다.

• 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식
• 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식으로 '상향식'이라고도 한다.

 

Top-Down (재귀)

• 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
• dp[n]의 값을 찾기 위해 위에서 부터 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식으로 '하향식'이라고도 한다.