다이나믹 프로그래밍의 조건
- 최적 부분 구조
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. - 중복되는 부분 문제
동일한 작은 문제를 반복적으로 해결해야 한다.
피보나치 수열 같은 것들을 구하고자 할 때 사용해볼 수 있다.
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(4))메모이제이션 (Memoization)
메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나
한 번 계산한 결과를 메모리 공간에 메모하는 기법
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
Top down vs Bottom up
Top down 방식은 하향식이고 Bottom up 방식은 상향식
DP의 전형적인 형태는 Bottom up 방식이다.
결과 저장용 리스트는 DP Table이라고 함.
Top down방식으로 피보나치 수열을 DP로 구해보면
dp = [0] * 100 # 메모이제이션으로 우선 100개의 원소를 가진 결과값을 초기화해놓는다.
def fibo(x): # 재귀함수로 구현한 피보나치 함수
if x == 1 or x == 2:
return 1
if dp[x] !=0: # 계산이 되었다면 무조건 배열의 원소는 0이 아니게 되므로 계산된적이 있다면 그대로 반환해준다.
return dp[x]
dp[x] = fibo(x-1) + fibo(x-2) # 계산이 되지 않은 경우
return dp[x]
print(fibo(99))Bottom up 방식으로 피보나치 수열을 DP로 구해보면
dp = [0] * 100 # 계산결과를 저장하기위해 모든 배열을 0으로 초기화해서 저장함.
dp[1] = 1
dp[2] = 1
n = 99
for i in range(3,n+1): # 반복문으로 구현해서 결과값들을 저장해놓는다.
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])이렇게 메모이제이션을 이용한다면 시간복잡도를 O(N) 이 나온다.
다이나믹 프로그래밍 vs 분할 정복
다이나믹 프로그래밍과 분할정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복
다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
다이나믹 프로그래밍 문제에 접근하는 방법
그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토해야함
재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있다.
개미 문제
import sys
n = int(sys.stdin.readline())
li = list(map(int,sys.stdin.readline().split()))
dp = [0] * 100
dp[0] = li[0]
dp[1] = max(li[0],li[1])
for i in range(2,n):
dp[i] = max(dp[i-1],dp[i-2]+li[i])
print(dp[n-1])1로 만들기
import sys
x = int(sys.stdin.readline())
dp = [0] * 30001
for i in range(2,x+1):
dp[i] = dp[i-1] + 1
if i % 2 == 0:
dp[i] = min(dp[i],dp[i//2]+1)
if i % 3 == 0:
dp[i] = min(dp[i],dp[i//3]+1)
if i % 5 == 0:
dp[i] = min(dp[i],dp[i//5]+1)
print(dp[x])효율적인 화폐구성
import sys
n,m = map(int,sys.stdin.readline().split())
li = [int(input()) for _ in range(n)]
inf = sys.maxsize
dp = [inf] * (m+1)
dp[0] = 0
for i in range(n): # i는 화폐 단위를 의미하고
for j in range(li[i],m+1): # j는 금액을 의미한다. 해당 금액인 li[i] 부터 m원까지를 확인한다.
if dp[j-li[i]] != inf: # 현재 금액에서 현재 확인하고있는 화폐 단위의 금액을 뺸 것을 만들 수 있다면
dp[j] = min(dp[j],dp[j-li[i]]+1) # 점화식 계속 최소값으로 갱신되는 방식
if dp[m] == inf:
print(-1)
else:
print(dp[m])금광 문제
import sys
t = int(sys.stdin.readline())
for _ in range(t):
n,m = map(int,sys.stdin.readline().split()) # 3,4
li = list(map(int,sys.stdin.readline().split())) # 1 3 3 2 2 1 4 1 0 6 4 7
dp = []
index = 0
for i in range(n):
dp.append(li[index:index+m])
index += m
#print(dp)
for j in range(1,m):
for i in range(n): # 모든 행 위치에 대해서
if i == 0: # 왼쪽 위
left_up = 0
else:
left_up = dp[i-1][j-1]
if i == n-1: # 왼쪽 아래
left_down = 0
else:
left_down = dp[i+1][j-1]
left = dp[i][j-1] # 왼쪽
dp[i][j] = dp[i][j] + max(left_up,left_down,left)
result = 0
for i in range(n):
result = max(result,dp[i][m-1])
print(result)
병사 배치 문제
import sys
n = int(sys.stdin.readline())
li = list(map(int,sys.stdin.readline().split()))
li.reverse() # 가장 긴 증가하는 수열을 만들기 위해서
dp = [1 for _ in range(n)] # li[i] 를 마지막 원소로 가지는 부분 수열의 길이
for i in range(1,n):
for j in range(i):
if li[j] < li[i]:
dp[i] = max(dp[i],dp[j]+1)
print(n - max(dp))