해당 글은 '이것이 코딩테스트다 with 파이썬' (나동빈 지음) 책 내용을 정리한 것입니다.
다이나믹 프로그래밍이란?
DP, 동적 계획법이라고도 불리는 이것은 메모리 공간을 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법이다.
다이나믹 프로그래밍의 조건
다이나믹 프로그래밍을 사용하기위해 다음과 같은 조건이 필요하다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열을 예시로 비교를 해보면 다음과 같다.
예시 : 피보나치 수열
DP를 사용하지 않은 구현 예시
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))일반적인 재귀호출 방법으로 피보나치 수열을 구현한 것이다. 하지만 이와 같이 구현할 경우 몇가지 문제가 발생한다.
시간 복잡도
- f(n) 함수에서 n이 커질 수록 수행 시간이 기하급수적으로 늘어난다.
- O(2^n)
- N = 30이면, 약 10억 가량의 연산을 수행한다.
- f(6)을 예시로 그림으로 표현하면 f(3)이 3번 호출되는 것을 볼 수 있다.
- f(n)에서 n이 커질수록 중복 호출되는 경우가 증가하고 f(100)일 경우에는 답을 도출하기 힘들 정도로 많은 시간이 소요된다.
DP 사용한 구현 예시
[Top-Down VS Bottom-UP]
- Top-Down : 재귀 함수를 이용해 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
- Bottom-UP : 반복문을 이용해 작은 문제부터 차근차근 답을 도출하는 방법
1. Top-Down
d = [0] * 100
def fibo(x):
if x == 1 or x == 2:
return 1
if d[x] != 0
return d[x]
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))한번 푼 문제는 저장해 놨다가 나중에 동일한 문제를 풀어야 할때(여기서 문제는 호출을 의미)이미 저장한 값을 반환하여 반복적으로 호출되는 상황을 막을 수 있다.
- 점선으로 표시한 부분은 호출이 되지 않은 경우로 메모이제이션을 통해 시간복잡도를 줄일 수 있다.
- O(N)의 시간복잡도를 가진다. 왜냐하면 한번 구한 결과는 다시 구해지지 않기 때문이다.
2. Bottom-UP
d = [0] * 100
d[1] = 1
d[2] = 2
n = 99
for i in range(3, n+1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])[추가]
- 때에 따라 dict 자료형을 이용하여 메모이제이션을 할 수 있다.
sys.setrecursionlimit()을 사용해 재귀함수 호출 제한을 완화할 수 있다.
