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

 

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

앞자에 글자를 따서 dp 라고도 불리고 동적 계획법이라고도 불린다.

 

 

"특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘"

알고리즘에서 주어진 문제에 접근하기위해 여러개의 하위문제의 풀이를 만들고,
그 풀이를 바탕으로 진행하여 최종적인 문제의 도달하는 알고리즘이라고 생각을 하면 된다고합니다.

 

위와 같은 설명으로는 dp를 처음 접하는 사람에서는 크게 와닿을 수 없는 이야기라서 간단하게 이야기를 하자면 
문제를 해결하기 위한 점화식을 찾아낸 후 점화식을 바탕으로 하위문제부터 차례로 구해나가서 최종적인 답을도출해내는 형태의 알고리즘

으로 설명을 할 수 있다.

 

그래도 예제 없이는 이해하기가 힘들어 예제를 예를 들어 설명을 해보겠습니다.

 

 

 

예제

 

피보나치의 수

Fibonacci sequence - Wikipedia

dp문제 중에 가장 기본이 되는 문제로 많이 언급이 되는 문제중에 하나인거 같아서 가져왔습니다.

피보나치의 수란 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열입니다. 즉

1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

형식으로 1 + 1 = 2, 1 + 2 = 3.. 형태처럼 계속해서 이전의 값을 참조해서 다음의 값을 만드는 식이라고 생각을 할 수 있는데

위의 식을 점화식으로 표현을 해보면 

형식으로 점화식을 세울 수 있고, 해당점화식을 코드로 대입을 해보면

int f(int n) {
	if(n == 0) return 0;
	if(n == 1) return 1;
	if(n == 2) return 1;
	return f(n) = f(n-1) + f(n-2);
}

형식으로 식을 세울 수 있다.

즉 위에 코드를 통해서 피보나치의 수라는 수열은 이전에 구해진 값을 참조하여 현재의 값을 도출해내는 방식을 사용하니 dp에서 사용하는 방식인 하위문제부터 차례로 구해나가서 최종적인 답을 도출해내는 방식과 같다는 것을 확인 할 수 있다.

 

 

해당 백준문제

2747번: 피보나치 수

 

퇴사

아래 링크를 통해 dp의 다른 예제도 확인해 볼 수 있다.

[백준] 14501번 - 퇴사, 15486번 - 퇴사 2 (C++)