[알고리즘] 동적 계획법(Dynamic Programming) & 메모이제이션(Memoization)

[알고리즘] 동적 계획법(Dynamic Programming) & 메모이제이션(Memoization) 동적 계획법이란? 주어진 문제를 세분화시키고, 최적의 해법을 찾아내기 위한 방법 DP를 이용하면 중복된 부분을 제거하여 다시 계산하지 않아도 되는 장점이 있다. 이는 연산의 효율을 높여주는데 큰 역할을 한다. 이를 알아보기 위해서는 '피보나치 수열'로 알아보기 쉽다 피보나치 수열은 위와 같은 구조로 '재귀 함수'를 통해 구현된다. 즉, index 0과 1을 제외하고 f(n) = f(n-1) + f(n-2)로 정의가 가능하다. 하지만, index의 값이 커질수록 호출되는 재귀함수가 무궁무진하게 커지는 문제가 발생한다. 지금처럼 빨간 원으로 묶인 부분은, 완전히 똑같은 부분을 다시 불러오는 모습을 볼 수 있..