［알고리즘 / Algorithm］ 중복되는 연산을 줄여주는 다이나믹 프로그래밍

Dynamic Programming Algorithm

다이나믹 프로그래밍 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 기본적으로 아래의 조건을 만족할 때 사용할 수 있다.

이러한 조건을 만족하는 대표적인 문제로는 피보나치 수열이 있다.

피보나치 수열을 memoization 기법을 사용하여 해결해보자. 메모이제이션은 한 번 구한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출하면 저장해둔 결과를 그대로 가져오는 기법이다.

이렇듯 재귀 함수처럼 큰 문제를 해결하기 위해 작은 문제를 호출하는 것을 Top-down 방식이라고 한다.

반면 작은 문제부터 답을 도출해나가는 Bottom-up 방식도 있다. 다이나믹 프로그래밍의 전형적인 형태로 이 방식에서 사용되는 결과 저장용 리스트를 DP table 이라고 부른다.

분할 정복과 비슷하지만 가장 큰 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다. 그래서 위의 코드처럼 이미 해결된 부분 문제에 대한 답을 저장해 놓았다가 나중에 동일한 문제를 풀어야 할 때 이미 저장한 값을 반환한다.