동적 계획법 - Dynamic Programming(DP)

참고 블로그 : https://hongjw1938.tistory.com/47

특징

Greedy와 매우 유사하다. 전 구간에 적용이 가능한 '부분 최적해'를 구해서, 이를 전 구간에 적용하는 방식은 유사하다. 하지만 몇가지 다른 점이 있다. 이에 대해 아래서 얘기해보자.

 

DP 사용 이유

멀리서 본다면 DP는 재귀와 굉장히 유사하다. 하지만 재귀의 단점을 보완한 방식이 DP이다.

예를 들어서, f(n)=f(n-1)+f(n-2)라는 피보나치 수열 공식을 구현한다고 가정하자. 이를 재귀로 구현해서 실행할때를 보자.

f(1000)을 구하려고 할 때, 내 코드는 과연 f(3)=f(1)+f(2)를 얼마나 반복하게 될까?

f(1000)=f(999)+f(998)

f(999)=f(998)+f(997)

...

단순히 f(5)=f(4)+f(3)=f(3)+f(2)+f(3)이므로, f3이 2번 계산된다. f(1000)의 경우엔트리 구조로 2의수십 수백승에 달하는 연산이 발생하게 된다. 이는 자바기준으로 자바 스택을 터뜨리기에 충분한 연산규모이다. 따라서 이를 방지하기 위해, 계산한 값을 메모리에 저장하며 연산해 나아가는것이 좋다. 이런 방식을 DP라고 한다.

 

DP 사용 조건

Greedy와 마찬가지로, 2가지 조건을 만족해야 한다.

1. 겹치는 부분 문제로 이루어져있어야 함

DP는 문제를 쪼갠 뒤 그 부분문제들의 "이미 구해진 값" 을 재활용하여 해를 구하는 방식이다. 따라서 커다란 한개의 문제를 쪼개서, 부분 문제로 나눌 수 있어야 한다.

2. 최적 해를 전체에 적용가능함

따라서, 특정 문제의 정답은 크기에 상관없이 항상 동일해야 한다.

 

 

DP와 Greedy의 차이

DP
모든 경우를 고려하되, 이미 계산한 결과를 재활용

(예: 피보나치 수열 → F(n) = F(n-1) + F(n-2))
이전 계산값을 저장하여 불필요한 재계산 방지
Greedy
앞만 보고 순간 최선의 선택을 함
(예: 동전 거스름 → 큰 단위 동전부터 사용 (단, 모든 경우에 최적해를 보장하지 않음))

 

DP 구현 방식

겹치는 부분 문제로 나누거나 최적해를 구하기, 혹은 점화식을 활용하는 등으로 반복해 점진적으로 나아가는 구현을 한다. 하지만 DP는 이전 값들을 '재사용' 해야 하므로, 이를 위해 이전 값들을 저장하는 구조(메모제이션)가 필요하다.

또한 아래 2가지 방식으로 최종 구현방향을 정할 수 있다.

dp[n]=dp[n-1]+dp[n-2]을 구현한다고 가정하자.

 

1 . Bottom-Up 방식 - 반복문 활용

dp[n]을 구해야 하는상황에서, dp 1구하고,,2 구하고,,, 3 구하고,,, 반복하는 구조이다. 반복문으로 0~n까지 반복해주면 된다.

 

 

2. Top-Down 방식 - 재귀 사용

dp[n]=dp[n-1]+dp[n-2]이므로 dp[n-1]과 dp[n-2]가 필요하겠다! -> 메모리에 존재하지 않는군-> 계산-> dp[n-1]=dp[n-2]+dp[n-3]이구나->메모리에 존재하지 않는군-> ..반복

 

 

두 방법 중 어느게 유리한가??

만약 고정된 답변이 존재했다면, 둘 다 말하지 않았을 것 이다. 답은..'문제마다 다르다' 이다. Bottom-Up방식이 겉으로는 더 빨라보일 수 있지만, 재귀로 풀어나가는 과정에서 메모리를 더 빨리 채우게 되어서 실행 시간이 더 빠른 경우도 있다. 이를 문제별로 잘 파악해서 시간 조건 내에 문제가 해결되도록 하는것이 중요하다.

 

Dynamic Programming 문제풀이들

https://chabin37.tistory.com/115

[JAVA] 백준 12865 평범한 배낭(with knapsack)

https://chabin37.tistory.com/116

[JAVA] 백준 1106 호텔

https://chabin37.tistory.com/117

[JAVA] 백준 3687 성냥개비

 

https://chabin37.tistory.com/118

[JAVA] 백준 2618 경찰차