6. 다이나믹 프로그래밍

1. 그리디, 구현, 완전 탐색 등의 아이디어를 문제를 해결할 수 있는지 검토

2. 풀이 방법이 떠오르지 않는다면 다이나믹 프로그래밍을 고려해보자

3. 재귀함수로 완전 탐색 프로그램을 작성해보고, 코드를 개선할 수도 있음

4. 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제

   메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 시키는 방법
   이미 계산된 결과는 별도의 메모리 영역에 저장하고 다시 계산 X
   탑다운 방식과 보텀업 방식

   동적 계획법, 다이나믹 프로그래밍
   자료구조에서는 동적 할당이 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 건데 다이나믹 프로그래밍에서 다이나믹은 별 의미 없이 쓰인 용어임

   조건 두가지

5. 최적 부분 구조

• 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아서 큰 문제 해결 가능

2. 중복되는 부분 문제

• 동일한 작은 문제를 반복적으로 해결

  대표문제)
  피보나치 수열 문제 - 재귀함수로도 구현 가능 => 지수 시간 복잡도를 가짐
  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
  점화식! 인접한 항들 사이의 관계식을 얻을 수 있다.
  $a_n = a_n-1 + a_n-2, a_1 = 1, a_2 = 2$

• 탑다운(하향식) 방식 - 메모이제이션 : 한번 계산한 결과를 메모리 공간에 메모, 같은 문제를 다시 호출하면 메모 결과를 가져옴, 값을 기록해서 캐싱이라고도 함
  시간 복잡도 : $O(N)$

# 메모이제이션
d = [0]*100

def fibo(x):
    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))

• 보텀업(상향식) 방식 - 다이나믹 프로그래밍의 전형적인 형태임

d =` [0]*100
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
print(d[n])

다이나믹 프로그래밍 vs 분할 정복
공통점 : 최적 부분 구조
차이점 : 부분 문제 중복, 다이나믹은 각 부분 문제들이 서로 영향을 미친다, 분할 정복(대표 예시 - 퀵 정렬)은 분할 이후에 자리잡은 피벗은 다시 처리를 안함

개미 전사 문제
$a_i = max(a_(i-1), a_(i-2) + k_i)$

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])

1로 만들기 문제
$a_i = min(a_(i-1), a_(i/2), a_(i/3), a_(i/5)) + 1$
1을 빼는 연산을 제외하고는 해당 수로 나누어 떨어질 때에 한해 점화식 적용 가능

x = int(input())
d = [0]*30001
for i in range(2, x+1):
    d[i] = d[i-1] + 1
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

효율적인 화폐 구성 문제

n, m = map(int, input().split())
array = []
for i in range(n):
    array.append(int(input()))

d = [10001] * (m+1)
d[0] = 0
for i in range(n): # n개의 화폐 종류를 훑으면서
    for j in range(array[i], m+1): #  ~ 목표 화폐값까지
        if d[j-array[i]] != 10001:
            d[j] = min(d[j], d[j - array[i]] + 1)

if d[m] == 10001:
    print(-1)
else:
    print(d[m])

금광 문제