다이나믹 프로그래밍 (DP) , 메모이제이션

안녕하세요 C++ 공부하고있는 대학생입니다.

이번에는 다이나믹프로그래밍 과 메모이제이션에 대해 정리하고자 합니다.

개념은 다음과 같습니다.

다이나믹프로그래밍 (DP)
큰 문제를 작은문제로 분할하여 계산하는 방식
TOP-DOWN , BOTTOM-UP 방식이 있다.

메모이제이션 기법
동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장하여, 동일한 계산을 피하고 계산속도를 향상시켜주기 위한 기법

바로 문제로 적용 해 보도록 하겠습니다. 대표적인 피보나치 수열 입니다.

피보나치 수열의 점화식은 다음과 같습니다.

A[n] = A[n-1] + A[n-2]

기존에 설명드렸던, 재귀방식을 이용하여 구현 해 보겠습니다.

#include <stdio.h>

int function(int num) {
	if(num == 1) return 1;
    else if(num == 2) return 1;
    else {
    	return function(num-1) + function(num-2);
    }
}

int main() {
	int num = 0;
    scanf("%d",&num);
    printf("구하고자 하는 %d번째 피보나치 수열은 %d 입니다.",num,function(num));
    
    return 0;
}

코드는 이렇게 간단하게 구현이 가능합니다. 그런데 만약에 이 연산으로 25번째 피보나치 수열을 구하고자하면 위의 코드로는 구할 수 없습니다. 왜냐하면 중복연산이 발생하여 계산이 기하급수적으로 늘어나기 때문입니다.
이를 방지하기 위해 사용하는것이 메모이제이션입니다.
메모이제이션은 배열을 하나 만들어서 연산된 값을 저장하여 기억하고, 중복된 연산이 나왔을 때, 해당 연산을 생략함으로써 계산속도를 보다 더 원활하고 빠르게 하기 위해서 사용합니다.

메모이제이션 기법을 사용한 피보나치 수열 코드는 다음과 같습니다.

#include <stdio.h>

int memo[1000];

int function(int num) {
	if(num == 1) return 1;
    else if(num ==2) return 1;
    else if(memo[num] !=0) return memo[num];
    else {
    	return memo[num] = function(num-1) + function(num-2);
    }
}

int main() {
	int num = 0;
    scanf("%d",&num);
    printf("구하고자하는 %d번째 피보나치수열은 %d입니다.",num,function(num));
    
    return 0;
}