다이나믹 프로그래밍의 사용 조건
1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다.(분할 정복{퀵 정렬} 의 특징이기도 함)
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음.
2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다. (이미 계산한 부분이 또 호출돼서 또 계산되는 것)
- 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
다이나믹 프로그래밍의 적용 가능 예
- 피보나치 수열
메모이제이션(Memoization) -> O(N) 시간 복잡도
- 다이나믹 프로그래밍을 구현하는 방법 중 하나(다이나믹 프로그래밍에 국한된 개념 아님!!)
- 한 번 계산한 결과를 메모리 공간에 메모하는 기법
- 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념
- 같은 문제를 다시 호출하면 메모했던 결과가 그대로 불러와 짐
- 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함.
- 결과 저장용 리스트 = DP 테이블
- 탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 한다.
- 저장한 것을 꺼내옴으로써 순차적으로 한 번씩만 실행되기 때문에 O(N)의 시간 복잡도를 보장한다.
# 피보나치 함수를 재귀함수로 구현(탑다운 방식)
d = [0] * 100
def fibo(x):
# 종료 조건(A1 이나 A2일 경우 반환)
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))
# 보텀업 방식
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
# 기존 계산했던 값을 꺼내고 거기에 추가로 계산함 => 바텀업
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])
'알고리즘 > 이론' 카테고리의 다른 글
이진 탐색(Binary Search) (0) | 2022.06.30 |
---|---|
정렬 알고리즘 시간복잡도 비교 (0) | 2022.06.22 |
계수 정렬(Count Sort) (0) | 2022.06.22 |
퀵 정렬(Quick Sort) (0) | 2022.06.22 |
삽입 정렬(Insertion Sort) (0) | 2022.06.22 |