DP(다이나믹 프로그래밍) _ Python

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

연산 속도와 메모리 공간을 최대한 활용하는 효율적인 알고리즘!

주어진 문제가 DP 문제임을 파악하는 것이 중요!

 

 

피보나치 수열 예시

 

점화식을 재귀 함수를 사용해 표현했을 때

fibo() 함수를 반복해서 호출하기 때문에 연산 횟수가 2^n 이 된다.

def fibo_re(x):
    if x == 1 or x == 2:
        return 1
    else:
        return fibo_re(x - 2) + fibo_re(x - 1)
        
print(fibo_re(4))

 

이렇게 매번 계산하도록 하는 과정을 해결하기 위해서 DP 사용

 

조건1. 큰 문제를 작은 문제로 나눌 수 있을 때

조건2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때

 

탑다운 방식(하향식)

메모이제이션 (캐싱)

: DP 기법 중 하나로, 한 번 구현한 결과를 메모리 공간에 저장해두고 같은 식을 호출하면 그 결과를 가져다가 씀

메모이제이션으로 구현한 피보나치 수열

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-2)+fibo(x-1)
    return d[x]

 

 

보텀업 방식(상향식)

- DP 테이블 사용

- 가능하다면 보텀업 방식이 권장됨. > recursion depth 오류 발생 가능(setrecursionlimit() 호출로 완화 가능하긴 함)

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])

---

~ 문제 풀이 ~

 

1로 만들기

 

알고리즘

 

보텀업 방식 

1이 될 때까지 계산하는 횟수를 구하는 것 -> 차례로 계산

우선 모든 수는 다 뺄 수 있기 때문에 기본으로 이전 수에서 1씩 더하기

나누기가 가능한 경우에 해당 몫 값에서 + 1로

ex) dp[25] 일 때 dp[24] = 4  + 1 로 생각할 수 있지만, 5로 나누어 떨어지기 때문에 dp[5] + 1 = 2 가 된다. 

 

코드

N = int(input())
dp = [0] * 30001

for i in range(2, N+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[N])

---

개미 전사

 

알고리즘

(보텀업 방식)

전체 셋을 모른다고 생각하고 하나씩 추가 될 때 어떻게 풀 지 생각하기

1. 현재 자리에서 최선의 값을 dp테이블에 저장

- 3번째 이상일 경우, 1+3 과 2 비교해서 큰 값을 그 자리의 최선 값으로 저장

 

코드

N = int(input())
array = list(map(int, input().split()))

dp = [0] * (N+1)
dp[0] = array[0]
dp[1] = max(array[0], array[1])

for i in range(2, N):
    dp[i] = max(dp[i-1], dp[i-2]+array[i])

print(dp[N-1])

---

바닥 공사

 

알고리즘

처음에는 그냥 1,2,3 만 생각해서 1 * 2 + 2 로 생각했는데 풀림

알고보니까 보텀업 방식으로 갔을 때, i-1에서 i가 되는법 1개, i-2에서 i가 되는 법 2개로 계산하는 거

어짜피 가로 길이 1 또는 2 이기 때문에 이 두가지만 고려하면 된다. 

 

코드

N = int(input())
# N + 1까지만 해도 되나?
dp = [0] * (N+1)

dp[1] = 1
dp[2] = 3

for i in range(3, N+1):
    dp[i] = (dp[i-2] * 2 + dp[i-1]) % 796796

print(dp[N])

---

 

효율적인 화폐 구성

알고리즘

**헷갈리는 점: dp에 저장하는 값은 만드는 way 개수가 아니라 최소로 만들 수 있는 수이다!

처음에는 array로 받은 모든 값을 dp 테이블에 1로 저장해뒀는데 그렇게 안해도 됨.

ㄴ> 이 경우에 입력받은 화폐 가치가 구하는 값(m)보다 클 경우 dp테이블 크기가 작아서 문제가 생김.

 

그냥 dp[0] = 0에서만 시작해도 가능...

어짜피 모든 화폐 조합이 +로 진행되기 때문에 상관없다. 

 

코드

N, M = list(map(int, input().split(' ')))
array = []
dp = [1001] * (M+1)
dp[0] = 0
for i in range(N):
    x = int(input())
    array.append(x)

for x in array:
    for i in range(x,M+1):
        if dp[i-x] != 1001:
            dp[i] = min(dp[i],dp[i-x]+1)

if dp[M] != 1001:
    print(dp[M])
else:
    print("-1")