8. 다이나믹 프로그래밍

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

• 메모리 공간을 약간 더 사용하여 연산속도를 비약적으로 증가시키는 방법
• 점화식(인접한 항들 간의 관계식)을 그대로 코드로 옮겨서 구현할 수 있다. (피보나치 수열)
• 이미 계산된 결과(부분 문제)를 별도의 메모리에 저장하여 다시 계산하지 않도록 한다. 
• 구현은 일반적으로 두가지 방식(top-down / bottom-up)으로 구성된다.
  • Top-down: 재귀함수를 이용하여 큰 문제 해결을 위해 작은 문제를 호출하는 방식
  • Bottom-up: 단순히 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 문제를 모아 큰 문제를 해결하는 방식 (전형적인 형태)
  • 결과 저장용 리스트는 DP 테이블이라고 불린다. 

DP 사용 조건

1. 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 동일한 작은 문제를 반복적으로 해결 가능해야 한다.

메모이제이션 

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

 

피보나치 수열 예제

1. 재귀함수 사용

def fibo(x):
	if x==1 or x==2:
    	return 1 # f(1),f(2)는 항상 1이기 때문
    return fibo(x-1) + fibo(x-2)

• 동일한 함수가 반복적으로 호출되기 때문에 연산횟수가 비효율적이다. (시간복잡도: O(2^n))
• 이러한 문제는 재귀함수를 통해 풀 수 있지만, dp를 활용하여 효율적으로 해결이 가능하다.

2. Top-down 구현 (재귀함수)

# 한번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0]*100

# Top-down 구현
def fibo(x):
	# 종료조건
    if x==1 or x==2:
    	return 1
    # 이미 계산o
    if d[x]!=0:
    	return d[x]
    # 아직 계산x
    d[x] = fibo(x-1)+fibo(x-2)
    
    return d[x]
    
print(fibo(99))

• 다음의 시간복잡도는 O(N)으로 줄어든다. 왜냐하면 한번 구한 결과는 다시 구하지 않기 때문! (댕효율적)

3. Bottom-up 구현 (반복문)

# dp 테이블 초기화
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])

• dp의 전형적인 형태이고, 메모이제이션이 사용되지 않는다. (그건 탑다운꺼)

 

실전 문제

1. 1로 만들기

dp 테이블: 연산 4개를 적절히 사용하여 x를 1로 만드는 최소 연산 횟수

x = int(input())

# dp 테이블 초기화
d = [0]*3001

# Bottom-up 구현
for i in range(2,x+1):
	# 1을 빼는 경우
	d[i]=d[i-1]+1
    # 2로 나눠떨어지는 경우
    if i%2==0:
    	d[i]=min(d[i],d[i//2]+1)
    # 3으로 나눠떨어지는 경우
    if i%3==0:
    	d[i]=min(d[i],d[i//3]+1)
    # 5로 나눠떨어지는 경우
    if i%5==0:
    	d[i]=min(d[i],d[i//5]+1)
        
print(d[x])

2. 바닥 공사

dp 테이블: 2*n(세로*가로) 바닥을 1*2,2*1,2*2 덮개들을 적절히 사용하여 채우는 모든 경우의 수

n = int(input())

# dp 테이블 초기화
d = [0]*1001

# Bottom-up 구현
d[1]=1
d[2]=3
for i in range(3,n+1):
	d[i]=(d[i-1]+d[i-1]*2)%796796
    
print(d[n])

3. 효율적인 화폐 구성

dp 테이블: 모든 금액에 대해 구성할 수 있는 최소한의 화폐 개수

메모이제이션 수행 → 각 인덱스는 '금액', 값은 초기에는 10001, 이후 최소 개수 저장 

n,m = map(int,input().split())

# n개의 화폐 종류 입력
arr = []
for _ in range(n):
	arr.append(int(input()))
    
# dp 테이블 초기화
d = [10001]*(m+1)

# Bottom-up 구현
d[0]=0
for i in range(n):
	for j in range(arr[i],m+1):
    	if d[j-arr[i]]!=10001: # (i-k)원을 만들수있는 경우
        	d[j]=min(d[j],d[j-arr[i]]+1)

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