[파이썬] 다이나믹 프로그래밍 기초

1. 다이나믹 프로그래밍이란 

다이나믹 프로그래밍은 

1. 작은 문제의 답을 이용해서 큰 문제의 답을 계산하고 

2. 각각의 계산결과를 기억하는 

방법이다. 

2. 조건 

다이나믹 프로그래밍을 이용하기 위해서는 두 조건을 만족해야 한다.

 

1. 최적부분구조

큰 문제의 정답을 작은 문제에서 찾을 수 있어야 한다. 

A라는 문제를 B와 C로 나누었다면 B의 결과와 C의 결과를 더한 값은 A와 같아야 한다. 그렇지 않으면 작은 문제로 나누어서 푸는 것이 틀린 접근이 된다. 

 

2. 중복된 하위 문제 

작은 문제들이 반복되서 이용되어야 한다.

작은 문제의 결과를 저장해서 재활용하기 때문에, 그 결과가 여러번 이용되어야 다이나믹 프로그래밍을 하는 의미가 있는 것이다. 

3. 방법, 재귀와의 비교 

피보나치의 수를 처음 배울 때는 무조건 재귀로 배운다. 다이나믹 프로그래밍보다 재귀를 먼저 배우기 때문이다.

하지만 그 방법은 효율적이지 못하다. 만약 F(n)이라는 함수로 피보나치의 수를 나타낸다면, n이 4일 때 F(4) = F(3) + F(2)이므로, F(3)과 F(2)를 계산해줘야 한다. 그러면 F(3)과 F(2)를 계산해주기 위해 F(2), F(1)의 값을 또 계산해줘야 한다. 

 

다이나믹 프로그래밍으로 접근하면 이전에 F(3)을 계산하기 위해 구해뒀던 F(2), F(1)을 저장해뒀다가 사용한 뒤에 F(3)도 저장한다. 그리고 F(4)을 계산할 때 F(3), F(2)를 꺼내서 쓴다. 이미 계산한 것을 다시 계산하지 않아도 되므로 더 빠른 계산이 가능해진다.

 

피보나치의 수를 다이나믹 프로그래밍으로 풀이한 아래 문제를 보면 차이를 알 수 있다.

 

[파이썬] 리트코드 509. Fibonacci Number 풀이

4. 예제 

다른 문제를 풀어보며 방법을 익혀보자. 

 

1463번: 1로 만들기

어느 정수를 1로 만들기 위한 최소 연산 횟수를 구하는 문제다.

만약 n이 10인 경우를 생각해보자. 2로 떨어지므로 2로 나눌 수 있고, 1을 뺄 수도 있다.

dp[n] = n이 주어졌을 때의 최소 연산 횟수 
if n이 10이라면 
	dp[10] = min(dp[9]+1, dp[5]+1) #1을 빼거나 2로 나누는 연산을 했으므로 +1  

즉 dp[10]이라는 '큰 문제'는 dp[9], dp[5]라는 '작은 문제'로 나누어서 해결할 수 있는 것이다. 

dp[15]는 3으로 나눈 dp[5], 1을 뺀 dp[14]라는 작은 문제로 나뉘어진다. 

 

그러므로, 3으로 나누어 떨어지면 dp[i] = min(dp[i-1], dp[i//3]) + 1

2로 나누어 떨어지면 dp[i] = min(dp[i-1], dp[i//2])) + 1인 것을 알 수 있다. 

 

n이라는 숫자를 

1. 2로 나누어 떨어지는 경우

2. 3으로 나누어 떨어지는 경우 

3. 어느쪽으로도 나누어지지 않는 경우 

이렇게 세 가지로 나누어 푼다고 하면 다음과 같이 풀 수 있다 

n = int(input())
dp = [0 for _ in range(n+1)]
dp[1] = 0
if n>1:
    dp[2] = 1 
for i in range(3,n+1):
    if i % 3 == 0 :
        dp[i] = min(dp[i-1],dp[i//3]) + 1 
    elif i % 2 == 0 : 
        dp[i] = min(dp[i-1],dp[i//2]) + 1 
    else:
        dp[i] =dp[i-1] + 1 
print(dp[n])