[Algorithm] 다이나믹 프로그래밍(Dynamic Programming)과 예시

 

이번에는 다이나믹 프로그래밍에 대해 알아보도록 하겠습니다.

저는 이부분을 공부하면서 진짜 공식 짜고 생각하는 과정이 진짜 알고리즘 답다고 느꼈습니다.

좀 어렵긴한데 공식이 들어맞았을 때 가장 희열이 느껴지는 것 같습니다.

 

 

---

 

▶ 메모이제이션 기법

한 번 구한 결과를 메모리 공간에 메모해 두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법입니다.
탑다운(메모이제이션), 보텀업 방식 두가지가 있습니다.

 

 

DF에서 가장 많이 예시로 드는 문제는 피보나치 수열 문제입니다.

이 문제의 구현을 보면서 하나씩 알아보도록 하겠습니다..

 

 

---

1. 탑다운(Top Down)

이 방법은 별로 추천하지 않으니 사용하지 말도록 합시다.

그래도 학습차원에서 무엇인지는 알아봅시다.

 

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

218922995834555169026

 

 

 

 

2. 보텀업(bottom up)

 

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

218922995834555169026

 

 

 

---

예제 문제로 좀 더 알아봅시다.

 

 

 

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 % 4 == 0:
    d[i] = min(d[i], d[i // 3]+1)
  
  if i % 5 == 0:
    d[i] = min(d[i], d[i // 5]+1)

print('answer : ', d[x])

26

answer : 3

 

 

 

 

2. 개미 전사

 

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('answer : ', d[n-1])

4

1 3 1 5

answer : 8

 

 

 

 

3. 바닥 공사

 

n = int(input())
d = [0]*1001

d[1] = 1
d[2] = 3
for i in range(3, n+1):
  d[i] = (d[i-1] + 2*d[i-2])%796796

print('answer : ', d[n])

3

answer : 5

 

 

 

 

4. 효율적인 화폐 구성

 

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):
    d[j] = min(d[j], d[j-array[i]] + 1)

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

2 15

2

3

answer : 5