Algorithm (1) - 다이나믹 프로그래밍 (Dynamic Programming)

✅ 개요

다이나믹 프로그래밍(Dynamic Programming)에 대한 이론 정리와 짧은 예제(피보나치 수열 함수) 구현

Ref : https://blog.naver.com/ndb796/221233570962

---

❓ 다이나믹 프로그래밍(Dynamic Programming)이란?

하나의 문제는 단 한번만 풀도록 하는 알고리즘을 의미합니다. 큰 문제를 작은 문제로 나눌 수 있고 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하다면 다이나믹 프로그래밍을 사용할 수 있습니다.

예시로는 피보나치 수열이 있습니다. 피보나치 수열은 \(f(n+2) = f(n) +f(n+1), \text{n is integer, n>0}\) 의 점화식을 가지고 있습니다.

---

🚩Dynamic Programming을 하지 않은 피보나치 수열 함수

import time

def fib_1(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fib_1(n-1) + fib_1(n-2)

start_time = time.time()

for i in range(1, 30):
    print(fib_1(i))

print('Calculation time is {}s'.format(time.time() - start_time, 2))

# Calculation time is 0.16456007957458496s

재귀적으로 구현한 피보나치 수열 함수입니다. 30까지의 피보나치 수열을 출력하는데 0.16초가 걸렸습니다. 50정도 넘는 숫자를 넣으면 정말 긴 시간이 걸립니다.

---

🚩Dynamic Programming을 적용한 피보나치 수열 함수

import time

ans = []
def fib_2(n):
    if n == 1:
        ans.append(1)
        return 1
    elif n == 2:
        ans.append(1)
        return 1
    else:
        now = ans[n-2] + ans[n-3]
        ans.append(now)
        return now

start_time = time.time()

for i in range(1, 1000):
    print(fib_2(i))

print('Calculation time is {}s'.format(time.time() - start_time))

# Calculation time is 0.006981611251831055s

이번엔 ans라는 list에 정답을 쌓아갔습니다. 그러면 계산 횟수를 엄청나게 줄이게 되어서 1000번째까지의 피보나치 수열을 출력하는데 0.007초밖에 걸리지 않게 됩니다!

이와 같이 정답을 메모리에 저장하는 기법을 메모이제이션 (Memoization)이라고 합니다.

---

🚩막대기 자르기

price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

def max_price(n):
    maxi = 0
    if n == 1:
        return 1
    for i in range(1, n+1):
        local = price[i] + max_price(n-i)
        maxi = max(maxi, local)
    # print(n, maxi) # 모니터링
    return maxi

문제 출처 : https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182

---

🚩 결론

Dynamic Programming을 쓸 수 있는 상황에서 잘 적용해 효율을 비약적으로 높일 수 있습니다.