다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍은 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 

 

다이나믹 프로그래밍으로 피보나치 수열의 문제 점을 해결할 수 있는데, 피보나치 수열은 특정한 숫자를 구하기 위해

 

특정한 숫자 바로 앞에 있는 수와 두 칸 앞에 있는 수의 합을 구하는 방식이다.

 

피보나치 수열은 동일한 문제를 다시 풀어 비효율적이라는 문제점이 있다.

 

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제에서 구한 정답은 그것을 포함하는

 

큰 문제에서도 동일하다는 가정 하에 사용이 가능하다. 다이나믹 프로그래밍을 통해 피보나치 수열의 문제점을 해결하기

 

위해서는 이미 계산한 결과를 배열에 저장함으로써 나중에 동일한 계산을 해야할 때 저장된 값을 단순히 반환하도록 한다.

 

[예제]

#include <stdio.h>

int d[100];

int dp(int x) {
	if (x == 1) return 1;
	if (x == 2) return 1;
	if(d[x] != 0) return d[x];
	return d[x] = dp(x - 1) + dp(x - 2);
}

int main() {
	printf("%d", dp(10));
}

 

예제를 살펴보면, 피보나치 수열 값을 구하는데, 여기서 특정한 값이 1이거나 2일 경우에는 1을 반환하도록 한다.

 

이유는 피보나치 수열은 기본적으로 맨 처음 숫자와 그 다음 숫자가 1로 시작하기 때문이다.

 

특정 값이 1과 2가 아닐 경우에는 특정한 값 바로 앞에 있는 수와 두번째 앞에 있는 수를 더하여 반환한다.

 

바로 여기서 피보나치 수열의 문제점을 해결하는데, 배열을 통해 이미 계산한 결과를 저장하고 나중에 동일한 계산을

 

할 때 저장된 값을 반환하는 방식이 사용된다. 이러한 방식으로 해결함으로써 한 번 구한 값을 다시 구하는 일이 없게 되어

 

시스템이 효율적으로 동작할 수 있다.

 

[결과]

다이나믹 프로그래밍(DP; Dynamic Programming) 결과

 

---

출처

https://blog.naver.com/ndb796/221233570962

20. 다이나믹 프로그래밍(Dynamic Programming)