[python] 🚨 다이나믹 프로그래밍

동적계획법(dynamic Programming)

• 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정(규칙을 찾아가는 과정)

---

😂이번 동적계획법에서는 저번에 다뤘던 동적계획법으로부터 좀 더 나아가서 좀 더 깊게 들어가보자~ 라는 마음으로 시작했는데... 너무 어렵다.... 오늘도 역시 기본으로 끝내지는 거같다....

➰피보나치 수열: 단순 재귀

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(s))
>>> 3

➰탑다운(Top down) vs 보텀업(Bottom up)

• ✅탑다운(메모이제이션) - 하향식이라고도 하며 재귀함수를 이용해 큰 문제를 해결하기 위해서 작은 문제들을 재귀적으로 호출하여 작은문제가 해결돼었을 떄 실제로 큰 문제 답까지 얻을 수 있고, 한 번 계산된 결과를 작성하는 메모이제이션 기법 사용
• ✅코드

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

#피보나치 함수를 재귀함수로 구현(탑다운 다이나기 프로그래밍)
def fibo(x):

    #종료조건(1혹은 2일 1을 반환)
    if x == 1 or x == 2:
        return 1

    #이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]

    #아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))
>>218922995834555169026

• ✅보텀업- 상향식라고도 하며 아래쪽에서 작은 문제를 하나씩 해결, 먼저 계산했던 문제들을 활용해서 그 다음에 문제를 차례로 해결(반복문을 활용)
• ✅코드

d = [0] * 100

#첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 2
n = 99

# 피보나치 함수 반복으로 구현(보텀업)
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n])
>>218922995834555169026

➰메모이제이션 동작 분석

• 이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠괸 노드만 처리할 것을 기대할 수 있다.

✅메모이제이션 사용 안 할 경우

✅메모이제이션 사용 할 경우

함수가 호출될때 마다 프린트를 사용해 사진과 같이 함수가 호출되는지를 살펴보면 얼마나 더 효율적인지 느낄 수 있을 걱 같다

d = [0] * 100

def fibo(x):
    print('f(' + str(x) + ')', end = ')
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

fibo(6)
>>> f(6)f(5)f(4)f(3)f(2)f(1)f(2)f(3)f(4)

함수 호출을 최소화하여 메모리 공간과 시간을 모두 절약할 수 있다. 이경우 수열 함수의 시간 복잡도는 O(N)이다.

➰다이나믹vs분할 정복

지금 학습하고 있는 다이나믹 프로그래밍과 저번에 학습했던 퀵 정렬과 같은 분할 정복은 어떤 차이와 비슷한 점이 있는지 파악해보자

✅공통점: 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.

• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

✅차이점: 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.

• 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
• 분할 정복 문제에서는 동리한 부분 문제가 반복적으로 계산되지 않는다.

➰다이나믹 프로그래밍 문제에 접근하는 방법

• 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토. (떠오르지 않는다면 다이나믹 프로그래밍을 고려)
• 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한뒤에(탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선.

---

❓문제풀이: 개미전사

1	3	1	5

4개가 다음과 같이 존재한다고 가정

• 두 번째 식량창고와 네번 식량창고를 선택했을대 최댓값인 총 8개의 식량을 빼앗을 수 있다.
• 식량창고 N 개에 대한 정보가 주어졌을대 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성해보자

문제 조건

✅문제 접근법
창고 0, 1, 2, 3으로 가정했을때 최적의 해를 계산해보자

a0 = 1
a1 = 3
a2 = 3 max(창고1, 창고2 + 창고0)
a3 = 8

사진으로 파악해보면 이해가 더 쉬울 거 같다.

500

✅코드

n = int(input())
array = list(map(int,input().split()))

d = [0] * 100

d[0] = array[0]
d[1] = max(array[0], array[1])

for i in range(2, n):
    d[i] = max(d[i-1],d[i-2] + array[i])
print(d[n-1])

출처: https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6