Dynamic Programming (동적 계획법)

: 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘으로, 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다.

→ 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘이다.

동적 계획법이 적용되기 위해 만족해야 하는 조건

• 부분 반복 문제 (Overlapping Subproblem)
• 최적 부분 구조 (Optimal Substructure)

Memoization

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

→ 중복되는 연산과정을 해결하기 위해 도입되었다.

memoization의 사용 조건

1. 작은 문제들이 반복된다.
2. 같은 문제는 구할 때마다 답이 항상 같아야 한다.

(만약 다른 변수가 작용하여 f(5)가 50이었다가 f(5)가 100이기도 한다면 사용할 수 없다.)

알고리즘 예시

int fibo(int number)
{
	if (number == 1 || number == 2)    // 기저 사례 처리
		return 1;
	if (memo[number] != -1)            // memoization 확인
		return memo[number];

	int fibo_number = fibo(number - 1) + fibo(number - 2);	// 부분 문제 수행 후 memozation 기록
	return fibo_number;
}