코딩테스트 - Chapter 08

다이나믹 프로그래밍

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

1. 다이나믹 프로그래밍

조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

메모이제이션 (캐싱; Cashing)
한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

탑다운 방식
재귀함수를 이용하여 다이나믹 프로그래밍 소스코드 작성 방식
큰 문제를 해결하기 위해 작은 문제 호출

보텀업 방식
단순히 반복문을 이용하여 소스코드를 작성하는 경우
작은 문제에서 차근차근 답을 도출

피보나치 함수

💡 재귀함수

def fibo(x) :
    if x == 1 or x == 2 :
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(99))

💡 메모이제이션 기법

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

2. 1로 만들기

1로 만들기

💡 보텀업 다이나믹 프로그래밍

x = int(input())

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

3. 개미 전사

개미 전사

💡 보텀업 방식

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

d = [0] * 100
d[0] = array[0]
d[1] = max(array[0], array[1])

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

print(d[n - 1])

4. 바닥 공사

바닥 공사

💡 보텀업 방식

n = int(input())

d = [0] * 1001
d[1] = 1
d[2] = 3

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

print(d[n])

5. 효율적인 화폐 구성

효율적인 화폐 구성

💡 보텀업 다이나믹 프로그래밍 (그리디 X)

n, m = map(int, input().split())
array = []

for i in range(n) :
    array.append(int(input()))

d = [10001] * (m + 1)
d[0] = 0

for i in range(n) :
    for j in range(array[i], m + 1) :
        if d[j - array[i]] != 10001 :
            d[j] = min(d[j], d[j - array[i]] + 1)

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