[알고리즘 개념] 동적 계획법 (Dynamic Programming) -(1)

인프런 강의 참고

동적 계획법 (Dynamic Programming) 이란

(출처 나무위키)

 

• 동적 계획법이란 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 이다.
• 즉, 답을 재활용!! 한다고 생각하면 쉽다.
• 기본적으로 분할 정복 알고리즘과 비슷하다.
• 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

+동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다.

 

 

예시

 

피보나치 수열

//재귀함수를 이용한 피보나치 수열 함수
int fib(int n)
{
	if (n == 1 || n == 2)
		return 1;
	else
		return fib(n - 2) + fib(n - 1);
}

하지만 이 방법은 많은 계산이 중복되기 때문에 효율적이지 않다.

피보나치 수열

방법1: Memoization (메모이제이션)

값을 저장해두고 재활용하는 방식이다,

int fib(int n)
{
	if (n == 1 || n == 2)
		return 1;
	else if (f[n] > -1)  //f[n] 이 -1보다 크다는 뜻은 이미 계산된 값이라는 의미
		return f[n];
	else {
		f[n] = fib(n - 2) + fib(n - 1);  //중간 계산 결과를 caching
		return f[n];
	}
}

• f 라는 배열을 -1로 초기화 해놓고 중간 계산 결과를 caching 해둔다.
• 중간 계산 결과를 caching 함으로써 중복 계산을 피한다.

 

그림으로 memoization 설명

 

방법2: Bottom-up 

 

int fib(int n)
{
	f[1] = f[2] = 1;
	for (int i = 3; i <= n; i++) {
		f[n] = f[n - 1] + f[n - 2];
	}
	return f[n];
}

f[3] 부터 f[n]까지 계산해 나가면서 이렇게 처음 값부터 최종값까지 배열을 채워나가며 계산해내는 방식이다.

 

[알고리즘 개념] 동적 계획법 (Dynamic Programming) -(2)에서는 이항계수에 대해 다뤄볼예정이다.