타뷸레이션

[메모이제이션 - Memoization] 메모이제이션이란?

메모이제이션이란? 메모이제이션이란 입력값에 대한 결괏값을 저장해둠으로써 같은 입력값에 따른 함수의 실행이 중복해서 일어나지 않도록 해주는 기법이다. DP로 문제를 풀 때 자주 등장하며, 함수의 중복 호출을 방지해 효율을 높여준다. 왜 쓰는가? 첫 번째와 두 번째가 1인 피보나치 수를 예로 들어보자. 피보나치 수를 재귀적으로 구한다면 위에서 볼 수 있듯이 fib(3), fib(4)등 앞선 피보나치 수가 여러 번 호출된다. 이때 fib(3), fib(4)이 각각 2, 3인 것을 저장해 두지 않는다면, fib(5), fib(6)이 무엇인지 구하기 위해 fib(3), fib(4)를 다시 구해야 한다. 이때 배열을 하나 만들어 이미 구해진 피보나치 수를 저장해둔다면 이 수고를 덜을 수 있다. 구하려는 수가 작다면..