Dynamic Programming VS Memoization

다이나믹 프로그래밍과 메모이제이션 알고리즘을 비교해보겠습니다.

 

다이나믹 프로그래밍은 모든 subproblem들을 전부 구해야하는 문제에 적용하면 좋습니다.

메모이제이션은 모든 subproblem들을 전부 구해야하는 경우, stack에서 왔다갔다하는 overhead가 있기 때문입니다.

 

반면,

메모이제이션은 subproblem을 전부 다 계산하지 않아도 되는 문제에 적용하면 좋습니다.

이전에 계산한 결과를 다시 계산할 필요가 없기 때문입니다.

 

코드를 통해 비교 및 이해를 해보도록 하겠습니다.

피보나치 수열을 다이나믹 프로그래밍과 메모이제이션으로 각각 구현해보겠습니다.

 

먼저 다이나믹 프로그래밍 기법을 이용한 피보나치 수열 구현 방법입니다.

 

int fibonacci(int n) {
    if (n < 2) {
    	return 1;
    }
    else {
    	return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

 

 

다음으로 메모이제이션 기법을 이용한 피보나치 수열 구현 방법입니다.

 

int fibonacci(int n) {
    if (mem[n] != -1) {
    	return mem[n];
    }
    else {
    	if (n < 2) {
        	return 1;
        }
        else {
        	return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

 

두 코드는 매우 유사하지만 다른 점이 있습니다.

메모이제이션 기법 코드의 경우 mem[n]의 값이 계산된 적이 있는지 판별하는 if 문이 존재합니다.