[코딩테스트][알고리즘] 4. DP( Dynamic Programming) 다이나믹 프로그래밍

 다이나믹프로그래밍의 기본적인 아이디어는 한 번 풀었던 문제를 다시 풀지 말자! 라는 것이다.

 

풀었던 문제의 답을 배열에 저장해놓고 필요할때 다시 사용함으로써 시간복잡도를 줄일 수 있게 된다.

 

이러한 과정을 메모이제이션(Memoization) 이라고한다. 

 

이러한 메모이제이션을 거치면 저장할 공간이 필요하기에 공간복잡도는 불리해지지만, 시간복잡도는 유리해진다.

 

 

DP는 분할정복기법( 해결했던 문제도 다시 계산 )을 개선 한 것 인데, 대표적인 예가 피보나치수열을 구하는 것이다.

 

피보나치 수열은 1 1 2 3 5 8 13 21 34 - - - 와 같이 D[i] = D[i-1] + D[i-2]  의 공식에 의해 진행되는 수들의 나열이다.

 

분할정복기법을 사용하여 피보나치 수열의 6번째 수를 구하는 과정은 다음과 같다.

 

(D[4] 과 같이 표현된 것이 계산과정, 3 5 8 같이 숫자로 표현 된 것이 저장된 값을 의미한다)

(참고로 D[1]과 D[2]는 1로 정의된 값이므로 계산과정을 거치지 않는다.)

 

D[6] = D[5] + D[4] = D[4] + D[3] + D[3] + 1 = D[3] + 1 + 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1+ 1 + 1 + 1 + 1

 

D[6] 을 구하는 과정에서 D[4], D[3] 이 반복적으로 계산되는 것을 볼 수 있다. 

 

다이나믹프로그래밍으로 구하는 과정을 살펴보면 다음과 같다.

 

D[3] = 1 + 1 = 2

D[4] = 2 + 1 = 3

D[5] = 3 + 2 = 5

D[6] = 3 + 5 = 8

 

두 방법을 비교 해봤을때 후자가 훨씬 간결한 것을 알 수 있다. 

 

다음 문제를 풀며 다이나믹프로그래밍에 대한 감을 익혀보자!

 

1. https://www.acmicpc.net/problem/2133

해설: https://ckdgus.tistory.com/15

 

2. https://www.acmicpc.net/problem/2718

해설 : https://ckdgus.tistory.com/16

 

3. https://www.acmicpc.net/problem/14852

해설 : https://ckdgus.tistory.com/17