[Algorithm] 동적 프로그래밍 | Dynamic Programming (DP)

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

 

다이나믹 프로그래밍을 사용하는 이유 

 

1. 메모리 공간을 더 사용하더라도, 연산 속도를 증가시키기 위해

2. 중복되는 연산을 줄이기 위해

 

 

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

 

1. 최적 부분 구조 (Optimal Substructure)

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때

2. 중복되는 부분 문제

- 동일한 작은 문제를 반복적으로 해결할 수 있을 때

 

 

다이나믹 프로그래밍 문제 접근 방법

- 그리디, 구현, 완전 탐색 등으로 문제를 해결할 수 있는 지 검토한 후 떠오르지 않는다면 다이나믹 프로그래밍을 고려해본다.

- 재귀 함수로 작성해본 후, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용할 수 있다면 bottom - up 방식을 고려한다.

 

 

메모이제이션 (Memoization)

: 한 번 계산한 결과를 메모리 공간에 메모하는 기법

    - 이전에 계산된 결과를 일시적으로 기록해 놓는 개념

    - 기록만 해놓고 활용하지 않을 수도 있음

    - 캐싱(Caching)이라고도 한다.

 

 

다이나믹 프로그래밍 소스코드를 작성하는 방식

 

1. 탑다운(Top-Down) 방식

- 큰 문제가 해결되지 않으면 그 때 작은 문제를 해결하는 방식

 

# 피보나치 수열

# 메모이제이션
m = [0 for _ in range(101)]

# 재귀

def fibo(x):
    if x == 1 or x == 2:
    	return 1
        
    if m[x] != 0:
        return m[x]
    
    m[x] = fibo(x-1) + fibo(x-2)
    
    return m[x]

 

2. 보텀업(Bottom-Up) 방식

- 보통 DP 문제의 풀이 방식

- 작은 문제부터 차근차근 답을 도출하는 방법

- 반복문 사용

 

# 피보나치 수열

dp = [0 for _ in range(101)]

dp[1] = 1
dp[2] = 1
n = 99

for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

 

※ recursion depth와 관련된 오류가 발생하면 sys 라이브러리에 포함되어 있는 setrecursionlimit() 함수를 호출하며 재귀 제한 완화 가능