알고리즘 공부 #2
다이나믹 프로그래밍
다이나믹 프로그래밍은 메모리를 적절히 사용해 시간 효율성을 비약적으로 향상시킬 수 있는 방법이다. 동적 계획법이라고도 한다. 이미 계산된 결과를 저장해두어 다시 계산하지 않도록 한다. 일반적으로 Top-down(하향식), Bottom-up(상향식) 두 가지 방식으로 구분된다.
전형적으로 Bottom-up 방식의 활용이 더 많다.
보통 아래와 같은 두 가지 사용조건을 만족할 때 사용한다.
1. 최적부분 문제구조(Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때
2. 중복되는 부분문제(Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 할 때
ex) 피보나치 수열
- 단순 재귀로 구현했을 때
def fibo(n) :
if x == 1 or x == 2 :
return 1
return fibo(n-1)+fibo(n-2)
이 때의 시간복잡도는 O(2N)이 된다.
- 다이나믹 프로그래밍으로 구현했을 때 (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))
위의 다이나믹 프로그래밍처럼 메모이제이션(Memoization)을 이용해 구현했을 시, 시간복잡도는 O(N)이다.
- 다이나믹 프로그래밍으로 구현했을 때(Bottom-up)
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])
- 메모이제이션(Memoization)
한번 계산한 결과를 메모리 공간에 메모해두는 기법으로 캐싱(Caching)이라고도 한다. 이는 탑-다운 방식이다.
결과 저장용 리스트는 DP 테이블 이라고 부른다.
Author And Source
이 문제에 관하여(알고리즘 공부 #2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lot9616/알고리즘-공부-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)