1. 동적계획의 이해와 구현

💡Dynamic Programming

1. 과거에 계산하였던 결과 활용
2. 점화식을 세워 문제 해결

피보나치 수열의 항을 DP로 구하기

지난 풀이

def ex_func(N) :
	if (N == 0) or (N == 1) :
    	return 1
    return ex_func(N -1) + ex_func(N - 2)
    

1️⃣Memoization

✅top-down 접근법
✅값을 기록하여 효율성을 높인다.

def ex_func(N) :
	if(fibo_list[N] != -1) :
    	return fibo_list[N]
    else :
    	fibo_list[N] = ex_func(N -1) + ex_func(N -2) <!--점화식-->
        
fibo_list = [1, 1] <!--초기값 설정-->

for i in range(1, 10000) <!--리스트 추가해놓기-->
	fibo_list.append(-1)

2️⃣Tabulation

✅bottom-up 접근법
✅빈 표에 값을 쌓아가는 방식

def ex_func(N) :
	fibo_list = [1, 1]
    for i in range(1, 10000) :
    	fibo_list.append(-1)
    for i in range(2, N + 1) :
    	fibo_list[i] = fibo_list[i - 1] + fibo_list[i -2]
     return fiboi_list[N]

2. 동적계획을 이용한 문제 해결

🧩예제 1 : 숫자카드 경우의 수 찾기

무한히 많은 1, 2, 3 숫자 카드를 가지고 있는 지선이가 임의의 자연수 N을 숫자 카드로 표현하려고 한다. 사용자로부터 자연수 N을 입력받아 N을 1, 2, 3 숫자 카드로 표현할 수 있는 경우의 수를 출력하면?
📍N = 2023인 경우
N = 2023 = 2020 + (3카드) = 2021 + (2카드) = 2022 + (1카드) 이다.
세 경우의 수는 절대 중복되지 않기 때문에
즉 점화식은 f(N) = f(N - 1) + f(N - 2) + f(N - 3)

N = input()
N = int(N)

dyn  = [1, 2, 4] <!--초기 3항 정의-->

for i in range(1, 10000) :
	dyn.append(-1)

for i in range(3, N) :
	dyn[i] = dyn[i - 1] + dyn[i -2] + dyn[i -3]
   
print(dyn[N - 1])

📍시간복잡도 : 빅세타(N)

🧩연습문제 : 타일 문제

1. 벽면의 크기는 가로 N(m) * 세로 2m이며, 빠뜨린 곳 없이 벽면 전부를 여러 개의 벽지로 채워야 한다.
2. 벽지는 가로형과 세로형이 있는데, 가로형은 가로 2(m) 세로1(m)이며 세로형은 가로 1(m) 세로 2(m)이다.
3. 벽지끼리 중첩되는 영역은 존재할 수 없다.

사용자로부터 자연수 N을 입력받아, 벽지를 시공하는 모든 경우의 수를 출력하는 Python 프로그램을 작성하라
📍입력 예시: 10
📍출력 예시: 89

N = input()
N = int(N)

dyn = [1, 2, 3]

for i in range(1, 10000):
  dyn.append(-1)

for i in range(3, N):
  dyn[i] = dyn[i-1] + dyn[i -2]

print(dyn[N-1])

3. 복잡한 상황에서의 동적 계획

🧩예제 1: 아르바이트 문제

[50000, 45000, 48000, 89000, 95000, 32000, 34000, 46000, 28000]
하영이는 최대한 많은 소득을 거두고 싶지만, 3일 연속 근로는 규정상 불가하다.
사용자로부터 일자 별 수당을 입력받아, 하영이가 거둘 수 있는 최대 소득을 출력한다면?

📍맨 마지막 9일차를 기준으로 생각한다면, 최대 소득을 거둘 수 있는 경우는 아래 셋 중 하나뿐이다.
(7일차 휴식 + 이틀 연속 근무) / (8일차 휴식 + 하루 근무) / (9일차 휴식)
1일부터 N일까지 거둘 수 있는 최대 수익을 f(N)이라고 한다면
f(9) = max(f(6) + 74000, f(7) + 28000, f(8))
📍위 식을 점화식 형태로 변환하면
f(N) = max(f(N-3) + g(N-1) + g(N-2), f(N-2) + g(N) + f(N-1))
*x일차 소득을 g(x)라고 한다.

money = [50000, 45000, 48000, 89000, 95000, 32000, 34000, 46000, 28000]
#초기항 정의
dyn[0] = money[0]
dyn[1] = money[0] + money[1]
dyn[2] = max(dyn[1], money[0] + money[2], money[1] + money[2])

for i in range(1, 10000) :
  dyn.append(-1)

for i in range(3, len(money)) :
  dyn[i] = max(dyn[i -3] + money[i -1] + money[i], dyn[i-2] + money[i] , dyn[i-1])

print(dyn[len(money) - 1])

📍시간복잡도: 빅세타(N)

🧩연습문제: 기차놀이

기차놀이를 위해 고려대와 연세대 총 N명의 학생들이 모였다. 기차놀이 뒤풀이를 위해 N명의 학생들을 연속된 몇 개의 기차로 나누되 총 기차의 수는 최소화하고자 한다. 한 기차에는 5인까지 탑승 가능하며, 학교 간 화합을 위해 기차 내 고려대생 수와 연세대생 수는 같거나 1차이여야 한다.
사용자로부터 학생들의 정보를 입력받아, 최소 기차 수를 출력하는 Python 프로그램을 작성하시오.

📍입력 예시: 고고연연연고고
📍출력 예시: 2

마지막 기차에 1명~5명 타는 경우를 각각 나눠 점화식을 세운다.
f(N)을 1명부터 N명까지 최소 기차 수라고 한다면,
f(N) = min(f(N-5) + 1, f(N-4) + 1, f(N-3) + 1, f(N-2) + 1, f(N-1) + 1)

그러나 고려대 학생과 연세대 학생이 같거나 1차이 나는 조건을 만족해야 한다.
예를 들어 [고, 연, 고..., 고, 고, 고, 고, 고] 라면 앞선 식을 만족할 수 없다.
g(x)함수를 만들어서
만약 차이가 1보다 작거나 같다면 1을(Yes) 출력하고
차이가 1보다 크다면 무한대(No)를 출력하도록 한다.

student = input()
student = list(student)

def g(N) :

  if (abs(N.count("고") - N.count("연")) > 1) : 
    return 0
  else :
    return 1
    
#이걸 구현하면 될 것 같은데
dyn[0] = 1
dyn[1] = 1 or 2
dyn[2] = 1 or 3
dyn[3] = 1 or 2 or 4
dyn[4] = 1 or 3 or 5


for i in range(1, 10000) :	
	dyn.append(-1)
    
for i in range(5, len(student)) :
  dyn[i] = min (dyn[i-5] + g(student[-5:]),
                dyn[i-4] + g(student[-4:]),
                dyn[i-3] + g(student[-3:]),
                dyn[i-2] + g(student[-2:]),
                dyn[i-1] + g(student[-1:])
  )
print(dyn[len(student) - 1])

*abs()함수는 절대값 구하는 함수
오류 고치기

4. 자료구조와 동적계획법

🧭Floyd-Warshall Algorithm

1. 출발지 A에서 도착지 B까지 갈 수 있는 경우는 다음 둘 중 하나이다
   1) 경유지 C를 거쳐서 간다.
   2) 경유지 C를 거치지 않고 간다.

   두 경우 중 어느 것이 최단으로 가는 것인지 알아내는 것이 목적이다.

def FloyWarshall(graph, graph_v, start) :

  for i in range(0, len(graph)) :
    for j in range(0, len(graph)) :
      <!--걸리는 시간이 0분인 것인지, 직행으로 갈 수 없어서 0으로 표시해놓은 것인지-->
      if (i != j) and (graph[i][j] == 0) :
        graph[i][j] = float('inf')
                
  for mid in range(0, len(graph)) :
      for start in range(0, len(graph)) :
          for end in range(0, len(graph)) :
             <!--경유했을 경우-->
              new_weight = graph[start][mid] + graph[mid][end]
              <!--경유했을 경우, 경유하지 않았을 경우 중 어느 것이 더 빠른지-->
              graph[start][end] = min(graph[start][end], new_weight)

  for i in range(0, len(graph)) :
      for j in range(0, len(graph)) :
          print(graph_v[i], '->', graph_v[j], '최단 거리 :', graph[i][j])

G = [[0, 30, 0, 20, 0],
    [40, 0, 0, -30, 0],
    [0, 50, 0, 0, 30],
    [0, 0, 0, 0, 60],
    [0, -20, 0, 0, 0]]
    
v = ['집', '경찰서', '소방서', '학교', '병원']

FloyWarshall(G, v, 0)