다이나믹 프로그래밍(동적 계획법) ex)백준 2839번 -python

 다이나믹 프로그래밍 dynamic programming, DP

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.

부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘에 유리

 

주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음,

그것을 결합하여 최종적인 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다.

 

예로 피보나치 수열, 점화식, 최단 경로 문제, 행렬의 제곱 문제 등 최적화에 사용

 

이미 계산한 결과를 별도의 메모리에 저장하여 다시 계산하지 않아 수행시간 효율이 좋다.

 

ex) 피보나치

function fib(n):
    if n = 0:
    	return 0
    elif n = 1:
    	return 1
    else:
    	return fib(n - 1) + fib(n - 2)

재귀함수로 풀었을 때

n = 5 라면 

fib(4) + fib(3)

(fib(3) + fib(2)) + (fib(2) + fib(1))

((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

이처럼 중복 계산되기 때문에 시간 복잡도는 O(2^n)

 

이걸 동적계획법(다이나믹 프로그래밍)을 이용하여 계산값을 저장하면

d = [] * 100 #계산 결과를 저장 리스트 초기화

function fib(n):
    if x == 1 or x == 2:
    	return 1
    if d[x] != 0:
    	return d[x]
    d[x] = fib(x - 1) + fib(x - 2)
    return d[x]

중복 계산이 줄어들어 시간 복잡도는 O(n)이 된다.

 

백준 2839번 문제를 다이나믹 프로그래밍을 통해 풀어보면

https://www.acmicpc.net/problem/2839

n = int(input()) #설탕 킬로그램
array = [3, 5]  
#결과값을 저장하는 리스트 초기화 최대 5000이니깐 5001
d = [5001] * (n + 1) 

#다이나믹 프로그래밍
d[0] = 0
for i in range(2): # 3 또는 5
  for j in range(array[i], n + 1): # 설탕 킬로그램
    if d[j - array[i]] != 5001:
      d[j] = min(d[j], d[j - array[i]] + 1) #최소로 만들 수 있는 경우
if d[n] == 5001: #설탕을 만드는 방법이 없을 경우
  print(-1)
else:
  print(d[n])

정말 이해가 어려운 코드지만 하나하나 적어보면서 하면 이해할 수 있을 겁니다.

저도 겨우 이해했음 ㅠㅠ

 

그리디 알고리즘과의 비교

동적 계획법이 가능한 모든 방법을 고려해야 한다는 단점이 있어

그리디 알고리즘이 등장했다.

현재에서 가장 최적의 해를 내는 그리디 알고리즘은 전체적인 정답이 될 수 없기에

적재적소에 사용해야 한다.