알고리즘 유형 6. 동적 계획법

동적 계획법 Dynamic Programming

 

- 줄여서 DP라고도 부릅니다.

- 문제를 쪼개고, 부분 문제들의 답을 구하는 과정을 반복하며 푸는 방식입니다.

- 동적 계획법을 구현하는 방법에는 재귀와 타뷸레이션(반복문)이 있습니다.

 

피보나치 수열이 동적 계획법 대표 문제입니다.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

F(5)를 구하고 싶다면 F(4)와 F(3)이 필요합니다.

F(5)라는 문제를 F(4)와 F(3)이라는 부분 문제로 쪼개어 풀어야하므로 동적계획법이 쓰인 것입니다.

 

 

 

 

메모이제이션 Memoization

 

- 한 번 구한 부분 문제의 답을 따로 저장해두고 필요할 때 꺼내쓰는 기법입니다.

- 캐싱(caching)이라고도 합니다.

- 메모이제이션은 DP와는 별개의 개념이긴 하나, DP 문제를 풀 때 시간초과가 나는 경우가 많아 시간 단축을 위해 같이 자주 쓰이는 개념입니다.

 

 

 

 

DP 구현 방법

1. 재귀

 

- 하향식 접근(Top-down) 방식입니다.

- 큰 문제에서 시작하여 점점 작은 부분 문제의 답을 구하기 위해 내려가는 방식입니다.

- 어떤 부분 문제의 답이 필요한 경우에 닥치면 그 때 구합니다. (Lazy-Evaluation 방식)

# 재귀로 피보나치 문제 풀기
cache = [-1] * 37
def f(n):
    if cache[n] != -1:
        return cache[n]

    cache[n] = n if n < 2 else f(n - 1) + f(n - 2)
    return cache[n]
    
print(f(36))

 

 

2. 반복문

 

- 상향식 접근(Bottom-up) 방식입니다.

- 작은 부분 문제부터 순차적으로 점점 큰 문제를 풀어가는 방식입니다.

- 모든 부분 문제의 답을 구해 두고 문제를 풉니다. (Eager-Evaluation 방식)

- 이렇게 푸는 방식을 타뷸레이션(Tabulation)이라고도 부릅니다.

# 반복문으로 피보나치 문제 풀기
fibo = [-1] * 37
for i in range(37):
    fibo[i] = i if i < 2 else fibo[i - 1] + fibo[i - 2]
    
print(fibo[36])

 

비교	Top-down	Bottom-up
구현	재귀	반복문
장점	직관적, 코드 가독성 좋음	시간, 공간 효율성이 좋음
단점	재귀함수 호출이 많이 느릴 수 있음	DP테이블을 채워 나가는 순서 파악이 힘듦