DP (Dynamic Programming) / 동적 계획법

• 하나의 큰 문제를 여러개의 작은 문제로 나누어 그 결과를 저장한 뒤 다시 큰 문제를 해결할 때 사용하는 패러다임.
  • 특정한 알고리즘이 아닌 하나의 문제를 해결하기 위한 패러다임.
• DP는 divide and conquer과 큰 문제를 작은 단위로 나누어 해결하는 면에서 비슷하지만 - DP는 부분문제가 중복되며 상위 문제 해결시 재활용된다.
  • Divide and conquer에서 부분문제는 서로 중복되지 않는다.
• 이미 했던 연산이 반복되는 현상을 보완하기 위해 나타났다.
  • 처음 실행하는 연산은 실시한 뒤 기록해 다음에 필요할 경우 기록해 둔 값을 가져온다.

DP를 적용한 피보나치 예시

• DP를 활용한 좋은 예시로 피보나치 수열이 있다.

// cpp

int fib(int &n) {
	if (n<=2) return 1;
    else return fib(n-1) + fib(n-2);
}

• 일반적으로 피보나치 수열을 구하는 함수를 만들때 이런식으로 재귀를 통해 n번째 수를 구할수 있다.

• 하지만 이런식으로 한다면 fib(5)만 구한다고 해도
  • = fib(4) + fib(3)
    • = fib(3) + fib(2) + fib(2) + fib(1)
      • = fib(2) + fib(1) + fib(2) + fib(2) + fib(1)
• 위처럼 많은 중복 연산을 필요로 한다.
• 이점을 보완하기 위해 DP가 고안되었다.
  • 이미 진행한 연산은 기록해 둔 다음 상위 문제 해결시 재활용한다.

Top down

// cpp

int fiboData[100] = {0,};

int fib(int n) {
	if(n<=2) return 1;
	if (fib[n]==0)
		fiboData[n] = fib(n-1) + fib(n-2);
	return fiboData[n];
}

• fibData 배열에 연산한 값들을 저장한다.
  • 다음에 중복 문제가 나올때 이 배열에서 결과값을 가져와 재연산 할 필요 없이 결과 반환이 가능하다.
• fib(n)을 호출할 때 n부터 작은수로 내려가는데 이처럼 문제 풀이가 위에서 아래로 진행되는 것을 top down 방식이라고 한다.

Bottom up

// cpp

int fib(int n) {
	fibodata[0] = 0;
	fiboData[1] = 1;
	for(int i=2;i<=n;i++) {
		fiboData[i] = fiboData[i-1] + fiboData[i-2];
	}
	return fiboData[n];
}

• bottom up방식은 top down방식과 반대로 문제 풀이가 아래에서 위로 진행된다.