[개념] 메모이제이션 기법에 대하여

메모이제이션이란?

 

"컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거해 프로그램 실행 속도를 빠르게 하는 기술"

 

피보나치 수열 예시

 

1. 일반적인 재귀함수를 이용할 경우

int fibonacci(int x){
	if(x<=2) return 1;
    
	return fibonacci(x-1) + fibonacci(x-2);
}

이미 계산한 내용을 계속 다시 계산하기 때문에, 필요없는 연산이 생겨 시간 복잡도가 증가한다. (O(2^n))

n= 5 일 때,

fibonacci(1) = 1

fibonacci(2) = 1

fibonacci(3) = fibonacci(1) + fibonacci(2)

fibonacci(4) = fibonacci(2) + (fibonacci(1)+ fibonacci(1))

fibonacci(5) = (fibonacci(1) + fibonacci(2))+(fibonacci(2) + (fibonacci(1)+ fibonacci(2)))

위와 같이 이미 계산한 값들을 다시 계산한다.

 

2. 메모이제이션 기법을 사용한 재귀함수

 

이미 계산한 내용은 저장하고, 연산할 때, 이미 저장된 값을 불러오면 된다. (O(n))

n = 5 일 때,

data[1] = fibonacci(1)

data[2] = fibonacci(2)

data[3] = data[1] + data[2] = fibonacci(3)

data[4] = data[2] + data[3] = fibonacci(4)

data[5] = data[3] + data[4] = fibonacci(5)

int data[100]; // 0으로 초기화된 배열

int fibo(int x){
	if(x<=2) return 1;
    
    // 이미 계산한 값을 갖고 있으므로 해당 값 리턴
    if(data[x] !=0) return data[x];
	else{
    	data[x] = fibo(x-1) + fibo(x-2);
        return data[x];
    }
}

 

* 참고한 블로그: hongku.tistory.com/161