알고리즘 : DP(Dynamic Programming)

1. 동적계획법(DP) 란?

큰 문제를 작은 문제로 나눠푸는 알고리즘이다. 이미 계산된 결과를 별도의 메모리에 저장하여 필요시 다시 계산하지 않고 사용한다.

 

요점은

'큰 문제를 작은 문제로 나눠 그 답을 저장하고 재활용한다' 이다. 자신이 한 것을 계속 기억하면서 문제를 푸는 방식이라고 생각한다.

---

2. DP를 쓰는 이유

DP를 쓰는 이유는 기억하는 것에 있다. '피보나치 수열'을 예로 들어보자

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

 

이를 구할 때 재귀를 사용한다면 이전결과와 또 그전 결과의 합으로 계속 구해나가게 될 것이다. 이럴 경우 시간복잡도가 O(n^2)

이렇게 되는 이유는 같은 계산을 반복하기 때문이다. 피보나치 수열 f(5) = f(4) + f(3)이다. 여기서 또 f(4)를 구하려면 f(4)=f(3)+f(2)다. 벌써 여기서 f(3)의 계산을 두번이나 반복하게된다. 이 둘의 계산결과는 같을 것임에도.

 

하지만 이 계산결과를 저장한다면 어떻게 될까? DP가 그 방법에 딱 알맞다. f(5) = f(4) + f(3)으로 처음에는 같지만 f(4)를 구하기 위해서 추가적인계산을 하지않고 이미 계산하고 저장한 값을 이용하기만 하면된다. 따라서 시간 복잡도가 

O(f(n))

(문제에 따라 다르다)

---

3. 적용 조건

DP는 정확히 언제 사용할 수 있는가? 2가지 조건을 만족할 때다

1) Overlapping Subproblems(겹치는 부분 문제)
2) Optimal Substructure(최적 부분 구조)

 

DP는 기본적으로 문제를 나누고 그 결과값을 재활용해서 전체문제를 해결한다.

그래서 동일한 작은 문제가 반복적으로 나타나는 경우 사용이 가능하다.

 

또한, 부분 문제의 최적결과 값을 사용해 전체 문제의 최적 결를 낼 수 있는 경우 사용이 가능하다. 그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다.

 

피보나치 수열은 동일한 작은 문제가 반복적으로 나타나며  n의 값이 커진다고 해도 특정 작은 문제들의 값은 동일하기에 DP사용이 가능했다.

---

4. 구현법

코드상으로 이를 구현하는 방법은 2가지가 있다.

Top-down 방식과 Bottom-up

탑다운은 '재귀' 바텀업은 '반복문'

 

1) 탑다운방식 - 재귀

dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식 피보나치 수열에서 사용되었다.

 

이미 계산에 사용된 값을 메모리에서 꺼내 활용하는 방식이다. 가장 최근의 값을 저장했다고 하여 Memorization 이라고도 한다.

 

2) 바텀업방식 - 반복문

아래에서 부터 계산을 수행하고 누적시켜 전체의 큰 문제를 해결하는 방식이다.dp[]라는 배열이 있다고 하면 dp[0]부터 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다. 피보나치 수열의 경우 f(0)와 f(1) 값을 미리 지정해주고 시작한다.

 

Tabulation이라고도 한다. 

 

반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 table-filling 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다.

 

오늘 푼 백준 1904도 바텀업방식으로 풀었다.

2024.09.03 - [코딩테스트/백준] - 20. 백준 1904 (실버3) : 01타일 _ python풀이 / DP

---

5. 정리

동적계획법(DP)는 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 알고리즘이다.

 

모든 해를 구하지 않고 최적의 해를 찾는 그리디 알고리즘과 대비된다. 그리디 알고리즘은 빠르지만 순간만을 고려해 항상 최적의 해를 찾는 것이 아니다.

 

하지만 DP는 느리지만 모든 방법을 검토하고 효율적인 값을 찾기 때문에 각자의 장단점이 있다.

시간 복잡도 : O(f(n)) (피보나치 수열 기준의 경우/ 다항식 수준, 문제에 따라 다르다)