[Algorithm] 다이나믹 프로그래밍(DP) 개념 및 적용

 

  목 차

• 개요
• DP를 사용하는 이유
• DP 적용하기
• DP 체감하기

 

 

---

 

  개요

 

 

  Dynamic Programmin(DP) 또는 동적 프로그래밍이라고도 하는데, DP는 복잡한 문제를 간단한 여러개의 문제로 나눠서 푸는 방식이다.

DP는 작은 문제가 반복하여 발생하고 이에 대한 해답을 저장해두고 재사용 하는 특징이 있다. 이렇게 함으로써 계산 속도를 크게 향상시킬 수 있다.

 

 

---

 

  DP를 사용하는 이유

 

 

DP는 주로 다음 두 가지 속성을 가진 문제에 적용된다.

 

 

1. 중복되는 문제 해결: 대표적으로 피보나치 수열의 예시가 있는데, 이 피보나치 수열을 재귀함수로 풀어본다면 코드는 아래 코드와 비슷할 것이다. Fn 을 계산하기 위해서 F(n-1) 과 F(n-2)을 계산해야 하지만, 이들 역시 F(n-3)과 F(n-4)를 필요로 한다. 수가 커질수록 같은 계산을 반복하는 수가 많아질 것이다. 이 문제를 해결하기 위한 방안이 DP이다.

 

function fibonacci(n: number): number {
	if (n <= 1 ) {
		return n;
	} 
	return fibonacci(n - 1) + fibonacci(n - 2);
};

Fibonacci 함수가 (5)일 때의 재귀함수 호출 트리

위 이미지를 참고하면 5 밖에 안 했는데도 중복되는 양이 상당한 것을 알 수 있다.

 

만약 여기서 DP를 적용한다면 저렇게 계산하지 않고, 한 번 계산을 하였다면 값을 저장하고 필요할 때 값만 가져다 사용하는 방식(Memoization)으로 중복되는 문제들을 해결하여 효율적이게 만들 수 있다.

 

 

시간 복잡도

 

DP 미적용: O(2^n)

DP 적용   : O(n)

 

 

2. 최적 부분 구조: 큰 문제의 최적 해결 방법이 작은 문제의 최적 해결 방법으로 부터 얻어질 수 있는 경우이다. 

 

 

---

 

  DP 적용하기

 

 

먼저 0과 1은 초기 값이기 때문에 먼저 넣어주었다.

 

자바스크립트에서는 존재하지 않는 값이면 undefined를 리턴하므로, undefined가 아닐 때(값이 존재할 때)는 재귀함수가 아닌 값을 리턴하고, 존재하지 않는다면 계산하고 저장한다.

let dp: number[] = [0, 1]  // DP배열

function fibonacci(n: number): number {
	if (n < 0) { throw new Error ('정수 넣으세요.')}  // 에러처리
	if (dp[n] !== undefined){  // DP 적용
		return dp[n];
	};
	dp[n] = fibonacci(n - 1) + fibonacci(n - 2);  // DP 적용
	return dp[n];
};

 

 

---

 

  DP 체감하기

 

다음 두 코드를 비교해보려고 한다.

console.time()으로 코드가 실행되는 시간을 측정하려고 하는데, 솔직히 차이가 너무 많이 나서..

DP를 적용하지 않은 코드는 값을 10만 하고,

DP를 적용한 코드는 50 까지 해보겠다.

 

 

DP 적용하지 않은 코드, 한 눈에 봐도 중복으로 계산된 것들이 보인다.

 

 

 

DP 적용된 코드, 50번을 하였는데도 이전 코드보다 빠른 모습을 보여준다.

그리고 계산은 50번으로 O(n)의 시간 복잡도를 보여준다.