파이썬 알고리즘 공부 - (3) 다이나믹 프로그래밍

📍다이나믹 프로그래밍 (동적 계획법)

: 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함

탑다운(하향식) : 이전 계산된 결과를 일시적으로 기록해놓는 개념(= 메모이제이션)을 활용. 

보텀업(상향식)

 

조건 

- 최적 부분 구조

- 중복되는 부분 문제

 

대표적인 예시 : 피보나치 수열

def fibo(x): # 1,1,2,3,5,8,13...
	if x == 1 or x == 2; #첫번째, 두번째 값이 1이라는 걸 명시 
    	return 1
    return fibo(x - 1) + fibo(x-2)
    
print(fibo(4))

 

다이나믹 프로그래밍을 활용하면 시간 복잡도를 줄일 수 있다. 

# 탑다운 다이나믹 프로그래밍 - 피보나치 수열
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])

 

* 다이나믹 프로그래밍과 분할 정복

공통점 : 모두 최적 부분 구조를 가질 때 사용할 수 있다.

차이점 : 부분 문제의 중복 -> 분할 정복에선 동일한 부분 문제가 반복적으로 계산되지 않음

 

EX)

# 보텀업 방식
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])

# 효율적인 화폐 구성

d = [10001] * (m+1) # 만들어야 하는 화페 m의 모든 인덱스 저장 공간

d[0] = 0
for i in range(n): #화폐 개수마다 확인
	for j in range(array[i], m+1):
    	if d[i-array[i]] != 10001:
        	d[j] = min(d[j], d[j-array[i]] + 1) # 기존의 만든 방식의 개수와 비교하여 더 작은 값
if d[m] == 10001: 
	print(-1)
else:
	print(d[m])

 

 

*가장 긴 증가하는 부분 수열 (LIS)

 

array = { 4,2,5,8,4,11,15}

result = {4,5,8,11,15} or {2,5,8,11,15}

 

dp 값의 의미

: 해당 값이 마지막 수열이 되었을 때 인덱스 값. 

 

dp = [1] * n

for i in range(1, n):
	for j in range(0, i):
    	if array[j] < array[i]:
        	df[i] = max(dp[i], dp[j] + 1)
            
print(n - max(dp)) #최소 병력 열외 수