> For the complete documentation index, see [llms.txt](https://koalas-organization.gitbook.io/koala_codingtest_study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://koalas-organization.gitbook.io/koala_codingtest_study/greedy_and_dp/dp1.md).
# 다이나믹 프로그래밍 1
하지만 우리의 일생은 위 그리디처럼 항상 독립적으로 일어날 수 없습니다.\
과거에 의존적인 상황에서는 그럼 어떻게 해야 효율적인 판단을 내릴 수 있을까요?
이런 상황에서 우리는 복잡한 문제들을 여러 문제로 나누어 푸는 방법을 사용합니다. \
~~아주 Dynamic하죠..?~~
DP를 가장 쉽게 설명하는 방법은 바로 우리가 쉽게 접해왔던 피보나치 수열입니다.
지금껏 피보나치 수열은 재귀함수로 많이 표현이 되어왔습니다.
하지만 이러한 함수 호출은 매우 치명적입니다. 위 그림을 보면 f(1)과 f(0)이 여러 번 출력됨을 볼 수 있습니다. 알고리즘 코드를 짜다보면 파이썬 에러 중\
*RecursionError: maximum recursion depth exceeded in comparison.*\
이 에러를 많이 보신 분들이 있을 텐데요. 이런 문제를 해결하기 위해 우리는 memoization, 즉 값을 저장해놓고 가져다 쓰는 방법을 사용할 수 있습니다. 📌**Memoization**은 시간/공간적으로 크게 효율적입니다.
다음으로 우리가 문제에 접근할 수 있는 방법을 알아봅시다.
피보나치 수열을 알아갈 때 위처럼 f(5)을 찾기 위해 f(4)와 f(3)을 탐색하는 직관적인 관점이 있습니다. 이를 우리는 📌**Top Down** 방식이라고 합니다.
하지만 애초에 f(1)부터 차근차근 구해놓고 시작해보면 어떨까요?\
피보나치 수열을 나타낼 때 우리는 1 1 2 3 5 8 13 21 34 … 이런 식으로 앞에서부터생각해낼 수 있습니다. 이렇게 애초에 아래에서부터 차근차근 구해놓고 시작하는 것을 📌**Bottom up** 방식이라고 합니다.
다음 피보나치 수열을 BOTTOM-UP 형식으로 나타내면 다음과 같습니다.
```python
N = int(input())
dp = [0]*(N+1)
def fib(num):
dp[num] = dp[num-1] + dp[num-2]
if N == 0 :
print(0)
else :
dp[1] = 1
for i in range(2, N+1):
fib(i)
print(dp[N])
```
* DP중 bottom-up(상향식)방법은 1+2부터 시작해서 작은 수부터 N+1 길이의 dp를 채워주고 마지막 결과값을 반환합니다.
* 트리 모양의 피보나치 수에서 **밑(자식노드)에서부터** 구하기 시작하는 것입니다.
TOP-DOWN은 다음과 같습니다.
```python
N = int(input())
dp = [0]*(N+1)
def fib(num):
if num <= 1 :
return num
elif dp[num] != 0:
return dp[num]
dp[num] = fib(num-1) + fib(num-2)
return dp[num]
print(fib(N))
```
* DP중 Top-down(하향식)방법은 우리가 구하고자 하는 수를 먼저 입력받습니다. N=100이라고 가정해봅시다.\
우선dp\[99] + dp\[98]을 가져와서 더해!라고 명령합니다.\
\> 그래서 dp\[99]랑 dp\[98]이 뭔데?\
\> dp\[99]와 dp\[98]를 찾기위해 fib\[99] 실행, fib\[98] 실행합니다.\
\> 그 안에서 또 98 97을 가져오라고 불러오면서 **아래로 내려가는** 형식입니다.
* 그래서 계속 물어보며 내려가다가 값이 나오는\
`if num <= 1 : return num`\
이 조건에서 1과 0이 나오면서\
그때부터 값이 채워지며 답하기 시작합니다.
* 이 때 elif를 보면, 만약 dp\[num]이 0이 아닌 경우 저장해두었던dp\[num]값을 가져오는 것을 볼 수 있습니다. 이것이 바로 **memoization** 입니다.
번외) 번외로, TOP DOWN 방식은 위에서 보는 것으로 알 수 있듯이 재귀함수로 구현됩니다. 파이썬은 Recursion의 한도가 시스템의 안정을 위해 정해져 있다는특징이 있습니다. 그래서 그 한도를 푸는 방법이 있는데, sys 모듈로 recursionlimit을 풀어주어야 하는 경우가 많습니다.
```python
import sys
sys.setrecursionlimit(10000) #재귀의 한도를 10000까지 풀어준다.
```
이 점이 파이썬이 C++에게 뒤쳐지는 이유인데요, 가끔 python으로는 풀리지 않은 백준 / 또는 대회 DP TOPDOWN 문제가 존재합니다. 하지만 코딩테스트에서는 그럴 일이 많이 없으니 걱정 마세요!
다음으로는 **2차원으로 memoization**하여 사용하는 DP 문제에 대해 알아볼까요?
{% embed url="" %}
이 문제를 그리디로는 풀 수 없습니다. 이 사실은 '가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.' 라는 문장만 봐도 알 수 있습니다.
규칙은 매우 단순합니다. 현재상태에서의 최선의 점수를 보려면 한 칸 앞 대각선 또는 두칸 앞 대각선을 보면 결정할 수 있습니다.
예를 들어 노란색 구간에서의 최대값을 찾고 싶다고 해봅시다 그러면 아래 1번 경우와 2번경우의 파란색 상황에서 적용해 가져올 수 있습니다.
만약 아래 3번 상황도 가져와야 하는 거 아닌가? 라고 생각했다면, 3번 상황은 1번 상황에 이미 반영되어 있을 것이므로 불가능합니다!
이를 모두 종합하여 이렇게 BOTTOM UP DP를 구현할 수 있습니다.
```python
t = int(input())
for i in range(t):
s = []
n = int(input())
for k in range(2):
s.append(list(map(int, input().split())))
for j in range(1, n):
if j == 1:
s[0][j] += s[1][j - 1]
s[1][j] += s[0][j - 1]
else:
s[0][j] += max(s[1][j - 1], s[1][j - 2])
s[1][j] += max(s[0][j - 1], s[0][j - 2])
print(max(s[0][n - 1], s[1][n - 1]))
```
위와 같이 1열부터 시작하여 BOTTOM UP 방식으로 2차원 채워나갈 수 있습다.
> ※ 더 생각해보기!
>
> 다음 문제는 어떻게 해결해야 할까??
>
> KAU 대학교의 학생식당은 맛없는 음식으로 악명이 높다. \
> 두 식당이 A,B 둘 있고 밥값은 $3, $4, $5 중 하나이다. 총 N일동안 각 식당의 가격이 미리 공지된다. KAU 대학교의 모든 학생은 반드시 하루에 정확히 한 끼를 학생식당에서 먹어야 한다. 최소의 비용으로 밥을 먹으려 하는데, 이 식당들의 음식은 너무 맛이 없어 연속으로 최대 이틀까지 같은 식당에서 밥을 먹을 수 있다.
>
> 즉, 예를 들면, 1일, 2일을 식당 A에서 밥을 먹었다면 3일째에는 반드시 식당 B에서 밥을 먹어야 한다. 아래 표는 총 8일간 식당의 가격표이다. 위 조건을 만족하면서 8일간 밥을 먹는 최소 비용을 구하시오.
>
> \
>
> 답은 3차원 DP로 DP\[식당 A, 식당 B]\[총몇 일째인지]\[연속된 날짜수] 로 표현하여 의존성을 생각하며 처리하는 것입니다.
## 풀어볼 문제
{% embed url="" %}
{% embed url="" %}
{% embed url="" %}
{% embed url="" %}
{% embed url="" %}
\[프로그래머스] 사칙연산
{% endembed %}