다이나믹 프로그래밍(Dynamic Programming)
DP
DP의 정의
큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘
DP가 필요할 때
피보나치 수열을 계산할 때 f(n)을 구하기 위해서 f(n-1)과 f(n-2)를 알아야 한다.
f(n-1)을 알기 위해서는 f(n-2), f(n-3)을 알아야 한다.
여기까지만 보더라도 많은 중복되는 계산이 굉장히 많다는 것을 알 수 있다.
DP는 이렇게 한번 계산한 값들을 다시 계산하지 않고, 저장해두고 reuse하는 방법이다.
Divide & conquor와의 유사성
위의 예시처럼 큰 문제를 작은 문제로 쪼개서 푼다는 의미에서 DP문제의 대부분은 D&Q의 개념을 공유한다.
하지만 피보나치를 보면 계산을 해야하는 양이 지수함수로 늘어난다.
우리는 이렇게 엄청나게 늘어나는 계산량을 DP를 통해 줄여줄 수 있다.
DP Basic Operation
DP의 연산량은 값들을 저장하기 위한 표를 채우는 것과 같다.
활용
DP Design
- 큰 문제를 작은 문제로 나눠서 볼 수 있는 반복을 찾아낸다.
(단, 작은 문제에서 구한 정답은 큰 문제에서도 동일해야한다) - 처음 진행되는 계산은 Look-up table을 사용해서 저장하고 재사용한다.
DP Analysis
DP의 Time Complexity는 Look-up table의 cell의 연산량 = # subproblems * # time/sub
두가지 방식
- 탑다운(Top-Down): 재귀를 이용해서 가장 큰 덩어리부터 접근해서 작은 덩어리로 내려간다. 메모이제이션을 사용한다.
- 바텀업(Bottom-Up): 반복문을 이용해서 가장 작은 덩어리부터 큰 덩어리로 접근한다.DP 테이블을 사용한다.
일반적으로는 바텀업 방식을 더 많이 사용한다.(반복문이 재귀보다 리소스 덜 사용)
모두 계산을 할 필요가 없을 때
우리가 찾고자하는 값까지 도달하기 위해 그 전의 모든 값이 필요하지 않을 때는 dictionary같은 자료형이 더 유리할 수 있다.
