Dynamic Programming(동적계획법) 정리

모든 경우의 수를 고려해서 최적의 값을 찾아야 할 때 종종 사용되는 알고리즘이다.

DP를 사용하기 위해서는 2가지 조건이 붙는다.

첫 째, 큰 문제가 작은 문제로 분할될 수 있고 분할된 문제들은 서로 중복된다. (Overlapping Sub-problems)
둘 째, 분할된 작은 문제들의 답을 구하면, 그 답을 큰 문제들을 구하는 데 사용할 수 있다. (Optimal Substructure)

모든 경우의 수를 고려해야 할 때 보통 재귀함수 사용을 많이 떠올리게 된다.
그런데 변수범위가 큰데 반복문과 재귀함수가 모두 사용될 경우 시간 복잡도가 O(2^n)이 되어 실행결과 최대 콜스택 초과 되는 경우를 초래하기 쉽다.

참고로 피보나치 수열을 재귀함수로만 구현한 코드에서 fib(50)을 수행하면 140초 가량이 지나야 결과를 받아볼 수 있다.
하지만, DP를 적용하면 0.1초도 걸리지 않고 결과를 즉시 볼 수 있다.

DP를 적용하는 방식은 크게 2가지로 나뉜다.

첫 째, Recursion & Memorization (Top-Down)
가장 큰 문제를 정의해서 base case까지 접근하는 것은 일반적인 재귀함수 사용법과 같지만, 매번 결과를 Cache로 이용할 배열과 같은 공간에 저장해 두고, 재귀호출 시 한번 계산된 값이 있는 지 Memo공간에서 먼저 확인해서 계산한 적이 있으면 저장공간에 있는 값을 그대로 리턴하는 방식이다.
이 방식을 성공적으로 적용할 시 DP방법 중 실행속도가 가장 빠른 방식이라 할 수 있다.
단, 이 방식을 적용할 시 반복문 사용하면 안된다!

둘째, Iteration & Tabulation (Bottom-Up)
반복문을 이용하여 가장 작은 문제부터 해답을 구해서 가장 큰 문제까지 연쇄적으로 해답을 구하는 방식이다.
보통 반복문과 배열을 이용하고, 배열의 첫 번째 arr[0] 값은 초기화 해줘야 한다.

시간복잡도와 DP를 접하기 전에는 반복문이든 재귀함수든 그냥 문제 푸는 데 필요할 것 같으면 아무 생각 없이 가져다가 썼는데 이제는 어떤 알고리즘이 필요한 문제인지 먼저 생각하고 그에 따라 푸는 방식이 얼마나 중요한 지 조금 알 것 같다.