(상태에 따른) 계산 결과를 저장해 두었다가 다음 계산에 활용하는 방법으로 공간복잡도를 희생해서 시간복잡도를 줄이는 기법이라고 생각하면 됨
(나이브하게 생각하면 이렇다는 거지 수업시간에 이렇게 쓰면 뒤짐 내가 해봄)


잘 알려진 예로 피보나치 수열을 구하는 프로그램을 단순히

int fib(int n)
{
   if (n <= 1)
      return n;
   return fib(n-1) + fib(n-2);
}


이러면 fib(n)을 실행할 경우 fib(n-1)과 fib(n-2)가 독립적으로 실행되게 됨.
fib(3)을 실행하면 fib(2)와 fib(1)이 실행되는데 fib(2)에서 또 fib(1)과 fib(0)을 실행하게 되서 fib(1)을 두번 실행하는 꼴이 되서 시간상으로는 비효율적임.

그래서 이걸 해결하는 방법(?)으로 memoization이라는 기법이 있음. 


이미 계산이 완료된 상태(여기서는 n의 값 = 상태)에 대해서 계산을 다시 수행하지 않고 이미 계산이 완료되었을 때의 결과값을 return해주는 방식인데,

상태의 경우의 수가 많을 경우에는 쓸 수 없다는 단점이 있긴 하지만(깊이의 수도 많으면 못 씀)
만약 DP를 잘 짜서 상태의 경우의 수가 적절히 적다면 memoization을 쓰는 것이 효율적임.
피보나치의 상태의 경우의 수는 최대 n값에 비례하니까 memoization을 쓸 수 있음.


예를 들어 위의 피보나치 수열을 Memoization으로 풀면

int memo[MAX_N];

int fib(int n)
{
   if (n <= 1)
      return n;
   if (memo[n] != 0)
      return memo[n];
   memo[n] = fib(n-1) + fib(n-2);    return memo[n];
}


fib(n)의 값을 구할 때
1. memo[n]이 0이 아닐 경우
-> 이미 memo[n]에 어떤 값이 들어있다
-> fib(n)을 계산한 적이 있다
-> fib(n)과 memo[n]은 같으므로 fib(n)의 값은 memo[n]과 같다.
-> memo[n]을 반환한다
2. memo[n]이 0일 경우
-> fib(n)을 계산한 적이 없다
-> fib(n)은 fib(n-1) + fib(n-2)이므로 memo[n]에 fib(n-1) + fib(n-2)를 넣는다. fib(n)과 memo[n]은 같기 때문.

-> memo[n]을 반환한다.

대충 이런 식으로 생각하면 됨.

중요한 건 memo[n]같은 걸로 이미 계산한 n의 값을 저장해두었다가 필요할 때 써먹어서 이미 계산한 n의 값에 대해서 중복해서 계산하지 않게 하는 거임.


잠이 부족해서 좀 이상한 부분이 있을 수도 있지만 댓글의 PS잘알 님들이 고쳐주실거임.