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

분할 정복

다이나믹 프로그래밍

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

• 하나의 문제는 단 한 번만 푸는 방법! 다이나믹프로그래밍 (이하 DP)
• 작은 문제를 해결하여 큰 문제를 해결하는 분할정복과 유사하다고 생각할 수 있지만, 분할정복의 경우 한번 풀었던 문제를 다시 푸는 비효율적인 단점을 가지고 있다. (일부 경우 제외 (병합정렬))
• 분할정복과 DP의 차이를 보여주는 대표적인 예시로는 피보나치 수열이 있다.
  • 피보나치 수열: 바로 앞과 앞앞 두 칸의 숫자의 합을 구해서 나타내는 수열
  • 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
  • 분할정복을 이용한다면 이미 구한 숫자들을 다시 계산하는 단점이 있다.

출처: https://blog.naver.com/ndb796/221233570962

• 위의 사진을 보면 13을 구하는게 2번, 12 3번, 11 3번 계산하는 것을 볼 수 있다.
• 이런 문제를 해결하기 위해 메모이제이션을 사용한다는 점!
• 이미 계산된 결과는 리스트에 저장을 해두고 필요할 때 꺼내서 사용한다.

📔 다이나믹프로그래밍(Dynamic Programming) 구현

# 피보: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
# 피보를 분할정복으로 구하는 방법
import time


def fibo1(x):
    if x == 1:
        return 1
    if x == 2:
        return 1

    return fibo1(x - 2) + fibo1(x - 1)


start = time.time()
print(fibo1(37))
end = time.time()
print(f'분할정복: {end - start}')

# 피보를 DP로 구하는 방법
dp = [0] * 100


def fibo2(x):
    if x == 1:
        return 1
    if x == 2:
        return 1
    if dp[x] != 0:
        return dp[x]
    dp[x] = fibo2(x - 2) + fibo2(x - 1)
    return dp[x]


start = time.time()
print(fibo2(37))
end = time.time()
print(f'다이나믹프로그래밍: {end - start}')

'''
24157817
분할정복: 6.408001184463501
24157817
다이나믹프로그래밍: 0.0
'''

 

📔 다이나믹프로그래밍(Dynamic Programming) 특징

• 보통 알고리즘을 풀 때 풀이가 너무 간단하지만 시간 초과가 발생하면 이 친구를 떠올리자.