[이코테]8장_다이나믹 프로그래밍

다이나믹 프로그래밍

• 다이나믹 프로그래밍은 동적 계획법이라고도 부른다
• 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미?
  • 자료구조에서 동적 할당(Dynamic Allocation): '프로그램이 실행되는 도중에 실행에 필요한
    메모리를 할당하는 기법'
  • '다이나믹': 별다른 의미 없이 사용된 단어
• 다이나믹 프로그래밍은 다음의 조건을 만족할 때 사용할 수 있다
  1. 최적 부분 구조 (Optimal Substructure)
     • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다
  2. 중복되는 부분 문제 (Overlapping Subproblem)
     • 동일한 작은 문제를 반복적으로 해결해야 한다

---

피보나치 수열

• 피보나치 수열 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다
• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
• 점화식이란 인접한 항들 사이의 관계식을 의미
• 피보나치 수열을 점화식으로 표현하면 다음과 같음

• 피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있다
  • 프로그래밍에서는 이러한 수열을 배열이나 리스트를 이용해 표현한다

• 피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있다
  • 𝑛번째 피보나치 수를 f(𝑛)라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같다

 

수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 이용함

 

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

피보나치 수열의 시간 복잡도 분석

• 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다
• 다음과 같이 𝒇(2) 가 여러 번 호출되는 것을 확인할 수 있다 (중복되는 부분 문제)

• 피보나치 수열의 시간 복잡도는 다음과 같다
  • 세타 표기법: 𝜽(1.618・・・ᴺ)
  • 빅오 표기법: O(2ᴺ)
• 빅오 표기법을 기준으로 𝒇(30)을 계산하기 위해 약 10억가량의 연산을 수행해야 한다

---

피보나치 수열의 효율적인 해법: 다이나믹 프로그래밍

• 다이나믹 프로그래밍의 사용 조건을 만족하는지 확인한다
  1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다
  2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다
• 피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족한다

---

메모이제이션 (Memoization)

• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나이다
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다
  • 값을 기록해 놓는다는 점에서 캐싱(Caching) 이라고도 한다

---

탑다운 VS 보텀업

• 탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 한다
• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다
  • 결과 저장용 리스트는 DP 테이블이라고 부른다
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다
  • 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다
  • 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다

 

 

 

<다이나믹 프로그래밍은 다음 조건을 만들 때 사용할 수 있다.>

1. 큰 문제를 작은 문제로 나눌 수 있다. 

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

메모제이션 기법: 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법, 값을 저장하는 방법을 <캐싱>이라고 한다. -> 한 번 구한 정보를 리스트에 저장, 다이나믹 프로그래밍을 재귀적으로 수행하다가 정보가 필요할 때는 이미 구한 정답을 리스트에서 가져옴

 

탑다운 방식: 재귀함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출한다.

보텀업 방식: 반복문을 이용하여 작은 문제부터 차근차근 답을 도출

 

<피보나치 수열 소스코드(재귀적)>-탑다운 방식

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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])

 

완전 탐색 알고라즘으로 접근했을 때 시간이 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인

 

보텀업 방식 권장

 

문제> 개미 전사: 문제 설명

• 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는
  여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다
• 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을
  빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가
  공격받으면 바로 알아챌 수 있다
• 따라서 개미 전사가 정찰병에 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진
  식량창고를 약탈해야 한다

• 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자

• 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 때 최댓값인 총 8개의 식량을 빼앗을
  수 있다. 개미 전사는 식량창고가 이렇게 일직선상일 때 최대한 많은 식량을 얻기를 원한다
• 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을
  작성하라

---

<문제> 개미 전사: 문제 해결 아이디어

• 예시를 확인해 봅시다. N = 4일 때, 다음과 같은 경우들이 존재할 수 있다
  • 식량을 선택할 수 있는 경우의 수는 다음과 같이 8가지이다
  • 7번째 경우에서 8만큼의 식량을 얻을 수 있으므로 최적의 해는 8이다

• 𝒂ᵢ = 𝑖번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최댓값)
  • 이렇게 정의한다면 다이나믹 프로그래밍을 적용할 수 있다

• 왼쪽부터 차례대로 식량창고를 턴다고 했을 때, 특정한 𝑖번째 식량창고에 대해서 털지 안 털지의 여부를
  결정하면, 아래 2가지 경우 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다

• 𝒂ᵢ = 𝑖번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최댓값)
• 𝑘ᵢ = 𝑖번째 식량창고에 있는 식량의 양
• 점화식은 다음과 같다

• 한 칸 이상 떨어진 식량창고는 항상 털 수 있으므로 (𝑖 - 3)번째 이하는 고려할 필요가 없다

n = int(input())
array=list(map(int, input().split()))
#앞서 계산된 결과를 저장하기 위해 dp 테이블 초기화
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))

---

<문제> 효율적인 화폐 구성: 문제 설명

• N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.
  이때 각 종류의 화폐는 몇 개라도 사용할 수 있다
• 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의
  화폐 개수이다
• M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하라

---

<문제> 효율적인 화폐 구성: 문제 조건

---

<문제> 효율적인 화폐 구성: 문제 해결 아이디어

• 𝒂ᵢ = 금액 𝑖를 만들 수 있는 최소한의 화폐 개수
• 𝑘 = 각 화폐의 단위
• 점화식: 각 화폐 단위인 𝑘를 하나씩 확인하며
  • 𝒂ᵢ₋ₖ를 만드는 방법이 존재하지 않는 경우, 𝒂ᵢ = min(𝒂ᵢ, 𝒂ᵢ₋ₖ + 1)
  • 𝒂ᵢ₋ₖ를 만드는 방법이 존재하지 않는 경우, 𝒂ᵢ = INF
• 𝑁(화폐 종류) = 3, 𝑀(만들려는 돈의 액수) = 7이고, 각 화폐의 단위가 2, 3, 5인 경우 확인해 보자
• Step 0 (초기화)
  • 먼저 각 인덱스에 해당하는 값을 INF(무한)의 값을 설정한다
  • INF은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미를 가진다
  • 본 문제에서는 10,001을 사용할 수 있다
  • 0원의 경우 화폐를 하나도 사용하지 않고도 만들수 있으므로 값을 0으로 설정한다. 

• Step 1
  • 첫 번째 화폐 단위인 2를 확인한다
  • 점화식에 따라서 다음과 같이 리스트가 갱신된다

• Step 2
  • 두 번째 화폐 단위인 3을 확인한다
  • 점화식에 따라서 다음과 같이 리스트가 갱신된다

• Step 3
  • 세 번째 화폐 단위인 5를 확인한다
  • 점화식에 따라서 다음과 같이 최종적으로 리스트가 갱신된다

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):
	for j in range(array[i],m+1):
    	if d[j-array[i]] != 10001 #i-k원을 만드는 방법이 존재하는 경우
        	d[j] = min(d[j], d[j-array[i]]+1)
if d[m] == 10001:
	print(-1)
else:
	print(d[m])