[코딩테스트 스터디 - 알고리즘 #3 Memoization Algorithm]
in study on Ct, Memoization
다음과 같은 내용을 공부합니다.
메모이제이션이란
피보나치 수열을 통한 예시
Memoization Algorithm
메모이제이션은 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복수행을 제거하여 전체적인 실행속도를 빠르게 해주는 동적 계획법의 핵심 기술입니다.
예시를 통해서 알아보는 Memoization
Memozaiont을 설명할 때, 가장 기본이 되는 피보나치 수열을 통해서 알아보겠습니다.
- 피보나치 수를 구할 때 n이 1과 2일 경우를 제외하고는 계속해서 (n-1), (n-2)항의 합으로 반복되서 계산이 됩니다.
이렇게 될 경우, 피보나치 수를 구하는 함수가 재귀적으로 실행되어서, 같은 인자값에 대해서 계속해서 반복하게 된다.
- 해당 문제를 보게되면, 일반적인 재귀함수의 형식으로 풀게되면, 계속해서 n이 1과 2가 될때까지 O(2^n)의 복잡도로 시간초과가 발생하게 된다.
따라서 이러한 단점을 보완할 수 있는 동적 계획법의 기법인 Memoization을 활용해야한다.
Memoization을 이용하여서 리스트에 값이 저장되어있으면, 다시 계산하지 않는 형식으로 접근해주면 시간을 줄일 수 있다.
Bottom-UP 방식