2021. 7. 1. 17:35ㆍFront-end/알고리즘
동적계획법이란?
큰 문제를 한 번에 해결하기 힘들 때 작은 문제로 나누어 푸는데,
이 때 이전에 계산한 값을 저장해두었다가 다시 사용하는 것이 핵심이다.
큰 문제를 작은 문제로 분할하여 푼다는 점에서 분할정복 알고리즘과 유사하지만, 한 번 계산했던 값은 저장한다는 점에서 (Memoization, 메모이제이션) 분할정복 알고리즘과 다르다.
동적계획법이 필요한 이유
그렇다면 왜 동적계획법이 필요한 것일까?
피보나치 수열을 예를 들어보자면, 점화식은 F(n) = F(n-1) + F(n-2)가 된다.
이는 간단하게 재귀함수만으로 구현할 수 있지만, 비교적 그렇게 어마어마하게 크지 않은 수인 50만 생각해보더라도 50을 구하기 위해서 불필요한 재귀가 일어나게 되어 엄청나게 많은 연산이 요구된다.
위의 그림에서도 알 수 있듯이 5를 구하기 위해서 다른 것들이 중복해서 계속 재귀적으로 호출되고 있다.
따라서 다이나믹 프로그래밍을 사용하여 이미 구한 값은 메모이제이션으로 저장을 해놓아서 불필요한 연산 횟수를 줄이면 성능이 매우 좋아진다. 그렇게 되면 시간복잡도가 O(n)으로 해결이 가능해진다.
동적계획법의 대표적인 문제
- 피보나치 수열
- 배낭 문제
동적계획법 방법
- Top-down 방식 : 하향식 방법으로, 가장 큰 문제를 방문 후 작은 문제를 호출하며 답을 찾는 방식이다. (메모이제이션+ 재귀함수를 호출해서 푼다.)
- Bottom-up 방식 : 상향식 방법으로, 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식 (반복문을 가지고 푼다)
* 대부분 문제에서 두가지 방식으로 모두 문제를 해결할 수 있으나 Top-down 방식이 재귀함수를 호출하기 때문에 Bottom-up 방식이 성능이 좋은 경우가 많다. 실제로도 입력값의 범위가 최대 100만인 것을 Top-down 방식을 이용했더니 메모이제이션을 사용했음에도 불구하고 call stack이 초과되었다는 메시지가 떴고, Bottom-up으로 수정하니까 풀렸다.
점화식
동적계획법 문제를 푸는 방법의 핵심은 점화식을 세우는 것이다.
주어진 문제를 보고 규칙이나 일반화시킬 수 있는 것을 찾아서 점화식으로 만든다.
그리고 점화식을 바탕으로 Top-down이나 Bottom-up 방식 중 하나를 선택하여 구현하면 된다.