[알고리즘]동적계획법-메모이제이션

메모이제이션 동적계획법에서 가장 중요한 것은 쪼개진 문제들의 해를 활용해서, 전체문제를 해결하는 것입니다. 문제의 해를 활용하기 위해서는 어딘가에 저장해야 하는데, 이를 메모이제이션Memoization이라고 합니다. 메모이제이션을 사용하면, 이전에 구했던 해는 다시 구하지 않고 재사용할 수 있으므로 알고리즘의 성능이 향상될 수 있습니다. 동적계획법을 활용해서 피보나치 수Fibonacci numbers를 구하는 과정을 보여드리겠습니다. 피보나치수란, 첫째항과 두번째항은 1이고, 그다음 항부터는 바로 앞의 두개의 항의 합인 수열을 의미합니다. 점화식을 세우고, 이를 활용해서 해를 구하는 과정 순서로 설명드리겠습니다. [표] 피보나치에 대한 점화식을 세우는 과정 해가 있다고 가정 Fibo(N)은 N번째 피보나치 수를 반환하는 함수라고 가정합니다. 아직 Fibo(N)을 구체화 하는 과정이 아닙니다. 단순히 있다고 가정하면 됩니다. 종료조건을 설정 피보나치 과정을 나타내면 위와 같습니다. 종...

원문링크 : [알고리즘]동적계획법-메모이제이션