[알고리즘] DP (Dynamic Programming)

 

 

 

개인 공부 후 자료를 남겨놓기 위한 목적이므로,
생략되거나 오류가 있을 수 있음을 알립니다.

 

---

 

DP는 두가지 종류가 있다.

1. 탑다운 DP
2. 바텀업 DP

그 중 탑다운 DP에 대해 알아보도록 하자.

 

 

0. 백트래킹

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

위 문제를 백트래킹을 이용해 풀어보자.

 

 

위와 같은 풀이가 나올 것이다.

 

그렇다면 이번엔 다음의 문제를 봐보자.

 

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

 

14501번) 퇴사 문제와 거의 일치하지만 N의 제한이 최대 1,500,000이므로 백트래킹으로는 무조건 시간초과가 발생하게 된다.

 

이러한 시간초과를 해결해줄 수 있는 알고리즘이 DP(Dynamic Programming)이다.

 

 

---

 

1. DP (Dynamic Programming)

이제는 백트래킹을 다음의 방식을 통해 짜보도록 하자.

 

1. 백트래킹으로 짠다.
2. 함수 형태를 바꾼다.(리턴방식으로)
3. 메모이제이션 추가.

 

 

먼저 위의 백트래킹 방식을 리턴방식으로 바꿔보자.

 

다음과 같이 나타낼 수 있을 것이다.

 

 

 

기존 백트래킹 방식 => 값을 쌓아가는 방식

 

리턴 방식 => 앞으로 벌 수 있는 최대 금액을 리턴하는 방식으로 변함.

 

이를 도식으로 표현하면 다음과 같다.

 

 

 

리턴 방식으로 함수가 변화함에 따라 값을 뒤에서부터 받아오는 형식이 되었다.

 

그렇다면 뒤부터 해당 날짜의 최대 금액을 저장하면서 가져온다면 불필요한 계산이 필요없게 되고,

 

이것이 Top-down(탑 다운) DP의 아이디어라고 할 수 있다.

 

코드로 표현해보자.

 

 

 

 

정리해보면 다음과 같다.

 

1. DP
   백트래킹이 너무 오래 걸린다 -> 하지만 중복 케이스를 많이 보고 있다.
   따라서 각 케이스의 정답을 저장해두고, 중복 케이스를 본다면 저장해놓은 값을 사용하자.
   
   
2. 메모이제이션
   정답을 저장해두는 행위 
   
   
3. Top-down DP
   재귀함수에서 메모이제이션을 이용해 시간 복잡도를 줄이는 방법