[자료구조 및 알고리즘] 동적 계획법 (Dynamic Programming, DP)

DP

 

도대체 이름이 왜 동적 계획법인지 궁금한 알고리즘이다. 지금까지 봤을 때는 점화식 세우기가 핵심인 알고리즘인 거 같다. 동적 계획법이란 최적화 이론의 기술로 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계방법이다.

 

문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출한다. 연산 횟수를 기가 막히게 줄여주며 이에 따라 시간복잡도가 개선되는 장점을 가지고 있다.

 

DP를 적용하기 위한 2가지 조건

 

동적 프로그래밍에 대해 찾아보는데 공통점이 여럿 있었다. DP를 사용하기 위해서는 두 가지 조건이 충족되어야 한다는 것이다.

 

1. 최적 부분 구조 - 전체 문제의 답을 부분 문제의 답을 이용하여 풀 수 있는 구조

 

2. 중복되는 부분 문제 - 부분 문제들에 중복되는 부분이 있는 문제

 

이에 완벽하게 부합하는 예제가 피보나치 수열 문제이다.

 

동작하는 방식 (Memoization VS Tabulation)

 

DP가 동작하는 방식은 2가지가 있다고 한다. 하나는 Memoization 다른 하나는 Tabulation. 두 가지 중 하나만 선택해서 문제를 해결해 나갈 수는 없다고 하니 두 가지 방법 모두 알아둬야할 거 같다. 이를테면 tabulation 방식으로 풀려고 했는데 부분 문제를 구하는 순서를 파악하지 못하면 memoization 방식으로 시도해볼 수 있을 것이다.

 

Memoization

 

중복되는 계산은 한 번만 하는 재귀 방식. 재귀 방식이기 때문에 너무 많이 사용하면 call stack이 쌓여 stackoverflow가 발생할 수 있다. 하지만 위로부터 계산하는 top-down 방식이기 때문에 필요없는 계산을 생략할 수 있다는 장점이 있다.

 

Tabulation

 

답을 구하기 위한 모든 계산을 table 방식으로 저장하는 for문 방식. 반복문으로 계산하는 bottom-up 방식으로 과부하로 인한 오류가 생길 일은 없지만 필요 없는 것까지 계산한다는 단점이 있다.

 

구분	Top-down	Bottom-up
구현	재귀	반복문
장점	직관적이라 코드 가독성이 좋음	시간과 메모리를 좀 더 아낄 수 있음
단점	재귀함수를 많이 호출해 느릴 수 있음	DP 테이블 채워나가는 순서를 알아야 함

 

코드

 

피보나치 수열을 계산하는 코드를 작성했다. 재귀방식은 40만 되도 계산시간이 10초 정도 소요되는 것 같은데 dp 방식으로 하면 바로 나온다. 누군가 계산해봤는데 3ms 정도 걸렸다고 하더라... 속도면에서 확실한 장점을 가지고 있다는 것을 체감했다. 이래서 알고리즘을 배우는 건가...

 

def dp_fibo(n):
    dp = [0] * (n+1)
    dp[1], dp[2] = 1, 1
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(dp_fibo(4)) # 3
print(dp_fibo(38)) # 39088169
print(dp_fibo(40)) # 102334155

 

점화식을 잘 세우자

 

아래 문제에서 느꼈다. 아... dp는 직관적으로 규칙을 찾아서 점화식 세우는 게 중요하구나... 하는 것을

 

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

9095번: 1, 2, 3 더하기