다이나믹 프로그래밍 1

다이나믹 프로그래밍이란? 🤔

Dynamic Programming, 줄여서 DP라 부른다.
동적 계획법 - 문제를 어떤 형태로 변형시켜 쉽게 푸는 방법을 의미한다.
큰 문제를 작은 문제로 나눠서 푸는 알고리즘

구현 과정 📌

1. Overlapping Subproblem
→ 큰 문제가 작은 문제로 세분화될 수 있고, 같은 방법으로 풀릴 때

2. Optimal Substructure
→ 큰 문제의 정답을 작은 문제의 정답들로 구성할 수 있을 때

💡 피보나치의 재귀 함수 코드

def fib(n):
    if n == 0: return 0
    elif n == 1: return 1
    return fib(n - 1) + fib(n - 2)

문제점 : 너무 잦은 함수 호출
→ 어차피 매번 답은 똑같은데, 시간을 단축시킬 방법은 없을까?

💡 메모이제이션 (Memoization)

동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장한다.
반복 수행 X → 시간 복잡도 단축 !

1. 작은 정답들을 저장할 수 있는 dp table을 만든다.
2. 문제를 해결하면서 작은 정답이 나올 때마다 저장
3. 이전에 해결한 정답을 요구하면, 다시 계산하지 않고 리턴

Overlapping Subproblem 조건에 해당 (큰 문제 해결 방법 = 작은 문제 해결 방법)

💡 메모이제이션을 적용한 피보나치

dic = {1: 1, 2: 1}

def memoization(n):
    if n in dic:
        return dic[n]

    dic[n] = memoization(n - 1) + memoization(n - 2)
    return dic[n]

💡 Top-Down 방법

큰 문제를 작은 문제로 나누고, 작은 문제의 정답을 이용해 큰 문제를 푸는 방법
위의 재귀함수 코드는 fib(n)을 먼저 넣어 작은 정답을 찾아나간다.
보통 재귀함수로 구현되면 Top-Down으로 생각하면 된다.

💡 Bottom-Up 방법

1. 크기가 작은 문제들부터 차례대로 푼다.
2. 점점 크기를 키워나가며 문제를 푼다.
3. 1, 2번을 반복하다 보면, 문제에서 원하는 정답을 구할 수 있다.

작은 문제들의 정답을 알고 있기 때문에 큰 문제의 정답도 구할 수 있다.

💡 Top-Down VS Bottom-Up

거의 대부분의 DP 문제는 두 방법 모두 풀이법이 있다.
처음에는 헷갈리는 재귀(Top-Down) 방법 보다, 눈에 보이는 Bottom-Up 방식을 추천한다 !

기본 문제 📁

🪄 피보나치 수 7

n번째 피보나치 수를 1,000,000,007로 나눈 나머지로 출력하는 문제
→ DP 문제를 풀 때, 웬만한 문제들은 메모이제이션을 하지 않으면 시간 초과가 나온다.

1. Bottom-Up 방식

피보나치 수는 fibo[i] = fibo[i-1] + fibo[i-2]이므로 for문을 사용해서 간단하게 구현할 수 있다.

MOD = 10**9 + 7

n = int(input())
fibo = [0, 1]
if n in [0, 1]:
    print(fibo[n])
    exit()

for i in range(2, n+1):
    fibo = [fibo[1], (fibo[0] + fibo[1]) % MOD]

print(fibo[1])

*모듈러 연산
어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다.

2. Top-Down 방식

Bottom-Up보다는 코드가 길지만 코드 로직을 쉽게 파악할 수 있다.
하지만 파이썬 특성상 함수 호출 시간이 느려서 시간 초과가 나올 확률이 매우 높다.

def fibo(x):
    if x == 0: return 0
    if x == 1: return 1

    if dp[x] != -1: return dp[x]
    dp[x] = (fibo(x-1) + fibo(x-2)) % MOD

    return dp[x]

import sys
sys.setrecursionlimit(1000010)
MOD = 10**9 + 7

n = int(input())
dp = [-1] * (n+1)
print(fibo(n))

*시간 초과가 나오는 코드

🪄 거스름돈

2원, 5원 동전만 이용해 N원을 만드려 한다.
이때, 동전의 최소 개수는?

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

dp[i] : 2, 5원으로 i원을 만들 때 동전의 최소 개수라고 하자.
초기 값 : dp[2] = dp[5] = 1

i원을 만드려면 i-2원 또는 i-5원을 만들 수 있어야 한다.
i-2원을 만드려면 i-4원 또는 i-7원을 만들 수 있어야 한다.
i-5원을 만드려면 i-7원 또는 i-10원을 만들 수 있어야 한다.

점화식 세워보기
→ 피보나치 수와 비슷한 형식 !

초기 값 → dp[i] = 1 (i = 2 or i = 5)
i원을 만들려면 i-2원 또는 i-5원을 만들 수 있어야 한다. → dp[i] = min(dp[i - 2], dp[i - 5]) + 1

1. Bottom-Up 방식

dp[i] = min(dp[i - 2], dp[i - 5]) + 1 이므로 for문을 사용하여 간단하게 구현이 가능하다.
코드는 6원부터 시작하니 4원 값을 설정하는 것에 주의

n = int(input())
dp = [float('inf')] * 100001
dp[2] = 1; dp[4] = 2; dp[5] = 1

for i in range(6, n+1):
    dp[i] = min(dp[i-2], dp[i-5]) + 1
    
if dp[n] == float('inf'): print(-1)
else: print(dp[n])

2. Top-Down 방식

Bottom-Up 방식보다 코드가 직관적이지만,
파이썬의 재귀 깊이가 최대 1000이라서 따로 재귀 깊이 설정을 해주어야한다.

def go(x):
    if x <= 5 or dp[x] != float('inf'): return dp[x]
    dp[x] = min(go(x-2), go(x-5)) + 1
    return dp[x]

import sys
sys.setrecursionlimit(200000)

n = int(input())
dp = [float('inf')] * 100001
dp[2] = 1; dp[4] = 2; dp[5] = 1
go(n)
print(dp[n]) if dp[n] != float('inf') else print(-1)

풀이 2. 수학

N을 5로 나눈 나머지가 짝수일 때 → 나머지는 2원으로 거슬러 준다.
N을 5로 나눈 나머지가 홀수일 때 → 나머지에 5를 더한 후 2원으로 거슬러 준다.
ex) N = 13, 몫 : 2 나머지 : 3 → 몫 : 1, 나머지 : 8

n = int(input())
if n == 1 or n == 3:
    print(-1)
    exit()
if (n % 5) % 2 == 0: print(n // 5 + (n % 5) // 2)
else: print((n // 5 - 1) + (n % 5 + 5) // 2)

🪄 1로 만들기

주어진 세 가지 연산을 이용해 1을 만드려고 할 때, 연산을 사용하는 횟수의 최솟값을 구하는 문제

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

점화식 세워보기
dp[i] : i를 1로 만들 때의 최소 연산 횟수라고 하자.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다. → dp[i] = dp[i / 3] + 1 (i % 3 = 0)
2. X가 2로 나누어 떨어지면, 2로 나눈다. → dp[i] = dp[i / 2] + 1 (i % 2 = 0)
3. 1을 뺀다. → dp[i] = dp[i - 1] + 1

위 3가지 경우 중 가장 낮은 값을 dp[i]로 초기화한다.

1. Bottom-Up 방식

점화식을 그대로 사용한다.

n = int(input())
dp = [float('inf')] * (n+1)
dp[n] = 0

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

2. Top-Down 방식

C++로는 통과를 하지만 파이썬은 통과하지 못한다.

def go(x):
    if dp[x] != float('inf'): return dp[x]
    if x % 3 == 0: dp[x] = min(dp[x], go(x//3) + 1)
    if x % 2 == 0: dp[x] = min(dp[x], go(x//2) + 1)
    dp[x] = min(dp[x], go(x-1) + 1)
    return dp[x]

import sys
sys.setrecursionlimit(1000050)

n = int(input())
dp = [float('inf')] * (n+1); dp[1] = 0
print(go(n))