[알고리즘 공부] 동적계획법
독적계획법
큰 문제를 한 번에 해결하기 힘들 때 작은 문제로 나누어 푸는데,
이 때이전에 계산한 값을 저장해두었다가 다시 사용하는 것이 핵심
큰 문제를 작은 문제로 분할하여 푼다는 점에서 분할정복 알고리즘과 유사하지만,한 번 계산했던 값은 저장한다는 점에서 (Memoization, 메모이제이션) 분할정복 알고리즘과 다름
동적 계획법이 필요한 이유
피보나치 수열을 예를 들어보자면, 점화식은 F(n) = F(n-1) + F(n-2)가 된다.
이는 간단하게 재귀함수만으로 구현할 수 있지만, 비교적 그렇게 어마어마하게 크지 않은 수인 50만 생각해보더라도 50을 구하기 위해서 불필요한 재귀가 일어나게 되어 엄청나게 많은 연산이 요구 됨.
위의 그림에서도 알 수 있듯이 5를 구하기 위해서 다른 것들이 중복해서 계속 재귀적으로 호출되고 있다.
따라서 다이나믹 프로그래밍을 사용하여 이미 구한 값은 메모이제이션으로 저장을 해놓아서 불필요한 연산 횟수를 줄이면 성능이 매우 좋아진다. 그렇게 되면 시간복잡도가 O(n)으로 해결이 가능해진다.
동적 계획법 방법
Top-down 방식
하향식 방법으로, 가장 큰 문제를 방문 후 작은 문제를 호출하며 답을 찾는 방식이다. (메모이제이션+ 재귀함수를 호출해서 푼다.)
Bottom-up 방식
상향식 방법으로, 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식 (반복문을 가지고 푼다)
