메모이제이션(Memoization)

오늘 처음 알게 된 DP 에서 중요한거 같은 Memoization!!!

메모이제이션이야 ....? 아니면 메모아이제이션이야....? 

 

쩃든,,,,

 

코드 두개를 비교 하면서 설명!

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

<코드 1>

fibo(int n) {
	if(n == 1 || n == 2) return 1;
    return (fibo(n-1) + ribo(n-2));
}

<코드 2>

fibo(int n) {
	if(Memoization[n] == 0)
    	Memoization[n] = fibo(n-1) + fibo(n-2);
	return Memoization[n];
}

 

처음에는 무슨 차이지... 싶었다.

코드 1은 그냥 한거고, 코드 2는 배열을 사용한것이다.

 

그런데 잘 생각해보면 코드 1에서 반복적으로 일어난 일들이 코드 2에서 메모이제이션을 하면서 안하고 바로 꺼내 쓸 수 있게 됬다.

 

피보나치와 관련된 문제들은 이런 방식으로 하면 시간이 매우 단축된다!!!!

 

실제로도 시간 복잡도는  Ω(1.6^n) 에서 Θ(n)로줄어든단다!!

 

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

메모이제이션 - 위키백과, 우리 모두의 백과사전

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

백준 문제는 메모이제이션과도 관련이 있는 문제인 듯 싶었다.

피보나치 문제기도 하지만!!!