[알고리즘] 다이나믹 프로그래밍 (동적 계획법)

동적 계획법 Dynamic Programming (DP)

동적 계획법은 주어진 문제를 하위 문제로 나눠 풀고 그 결과를 저장해 다음 문제를 푸는데 사용하는 알고리즘이다.

 

이는 분할 정복 Divide and Conquer과 비슷해보이지만 동적계획법에서는 하위문제가 서로 종속성을 가진다는 점이 다르다. 즉 문제를 풀고 그 답이 다른 문제에 영향을 끼칠 수 있다는 것이다. (= 메모이제이션)

 

동적 계획법의 핵심은 같은 문제의 중복 호출을 피하자는 것이다. 

동빈나님의 설명으로는 '하나의 문제를 단 한번만 풀도록 하는 알고리즘' 이라는 것이다.

 

 

동적계획법을 사용하기 적절한 문제의 특징은 이렇다.

1. 최적화 문제이다
2. 재귀적 구조를 가져 재귀 구현했을 때 중복 호출로 비효율이 발생한다.

 

최적화 문제라는 것은 하나의 문제에 여러개의 답이 존재하고 그 답들을 서로 비교할 수 있어 최선의 결과를 찾아야 하는 문제이다.

 

 

동적 계획법의 가장 쉽고 대표적인 예로 피보나치 함수가 있다.

 

피보나치의 기본 공식이 있다.

 

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

 

만약 F(5)를 알아내려면

F(4) + F(3)을 알아내야 한다.

 

또 저걸 알아내려면 F(4)와 F(3)을 알아내야하고....

또 F(3)과 F(2)를.... F(2)와 F(1)을...

 

이렇게 계속 가야한다.

 

이렇다보면 중복되는 부분이 생긴다.

 

그 중복을 피하기 위해 DP를 사용하는 것이다.

 

 

메모이제이션 Memoization

DP에서 이 중복되는 것을 따로 메모리에 저장해두었다가 필요할때 꺼내 쓰는 기법이다.

 

 

+참고

동빈나님 영상

https://youtu.be/FmXZG7D8nS4

21강 - 다이나믹 프로그래밍(Dynamic Programming) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #21 ]