메모이제이션? (memoization)

 

 

메모이제이션 은 값비싼 함수 호출의 결과를 캐싱하고 동일한 입력이 다시 발행할 때 불필요하게 다시 계산하는 대신 캐싱된 결과를 반환하는 프로그래밍 기술입니다.

 

동일한 입력으로 여러 번 호출되는 함수 또는 컴포넌트가 있을 때 유용합니다.

아래와 같이 활용 할 수 있습니다.

 

 

동적 계획법

• 복잡한 문제를 간단한 여러가지 문제로 나눠 푸는 방법
• 중복된 부분을 제외하여 한번만 계산하고도 구할 수 있어 시간,공간 복잡도를 감소시킴

 

피보나치를 구하는 방법 

 

1) 재귀 함수 호출

숫자가 커질수록 함수를 되풀이하므로 시간이 오래 소요된다. 시간복잡도:O(2^n)

static long fibo(int N) {
	if(N<=1)
    	return N;
    else
    	return fibo(N-1) + fibo(N-2);
}

 

 

2) 메모이제이션 활용

한 번 구한 계산을 더이상 계산하지 않고 가져다 쓰는 개념이라 시간이 줄어들 수 있습니다. 시간 복잡도:O(n) 

static long[] arr = new long[51]; // 저장 변수 선언

static long fiboMemozation(int N) {
	if(N == 0)
    	return arr[0];
    else if(N == 1)
    	return arr[1];
    else if(arr[N] != 0)
    	return arr[N];
    else
    	return arr[N] = fiboMemoization(N-1) + fiboMemoization(N-2);
}

 

 

N의 값이 커지면 커질수록 실행시간도 커집니다.

즉, 동적 계획법을 효율적으로 짜기 위해서는 메모이제이션을 활용할 수 있습니다.

 

 

 

 

 

 

 

---

references:

https://d2.naver.com/helloworld/9223303

https://gaybee.tistory.com/45