[WEEK04] 알고리즘_다이나믹 프로그래밍(DP)

[WEEK04] 알고리즘_다이나믹 프로그래밍(DP)

 

다이나믹 프로그래밍 특징

 

• 하나의 문제는 단 한 번만 풀도록 하는 알고리즘
• 메모이제이션(Memoization, 이미 계산한 결과는 배열에 저장함. Memorization이 아님)을 통해 동일 계산시 저장된 값을 단순히 반환하여 시간을 줄임 -> 메모리를 적절히 사용하여 수행 시간을 굉장히 단축시킨다.
• 일반적으로 탑다운(하향식, 재귀함수 이용), 바텀업(상향식) 두가지 방식으로 구현한다.
• 보통 바텀업이 전형적인 형태이다.

 

다이나믹 프로그래밍 사용 조건

 

1. 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 통해 큰 문제를 해결 가능한 구조
2. 중복 부분 문제(Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 해결할 수 있는 구조

피보나치 수열을 다이나믹 프로그래밍으로 풀 수 있는 이유는, f(n)을 구하기 위해서는 f(n-1)과 f(n-2)의(~ f(1)까지) 값을 구해야 하고(최적 부분 구조) f(n)을 구하기 위해서 f(n-1)이 동일하게 세 번 쓰이기 때문이다.(중복 부분 문제)

 

 

다이나믹 프로그래밍을 통한 문제 풀이

 

피보나치 수열 문제를 통해  탑다운 및 바텀업 방식을 알아보자

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

탑다운 방식 코드

## 탑다운 방식. 재귀 사용
import sys

input = sys.stdin.readline

N = int(input())
dp =[0] *100
# 피보나치 함수를 재귀함수로 구현, 탑다운 디피
def fibo(x):
    # 종료 조건(1 혹은 2일 때 반환)
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if dp[x] != 0:
        return dp[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    dp[x] = fibo(x-1) + fibo(x-2)
    return dp[x]

print(fibo(N))

 

바텀업 방식 코드

## 바텀업 방식

import sys
input = sys.stdin.readline

N = int(input())
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
dp = [0] * 91
dp[1] = 1
dp[2] = 1
# 피보나치 함수 반복문으로 구현, 바텀업 디피
for i in range(3, N+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[N])