✨나동빈님의 다이나믹 프로그래밍 강의를 보고 작성한 글입니다.
https://www.youtube.com/watch?v=5Lu34WIx2Us
다이나믹 프로그래밍?
다이나믹 프로그래밍은 메모리를 적절히 사용해서 수행 시간 효율성을 향상 시키는 방법이다.
- 동적 계획법이라고도 불린다.
- 다이나믹 프로그래밍은 top-down(하향식)과 bottom-up(상향식) 방식으로 구성된다.
일반적인 프로그래밍 분야에서 쓰이는 동적과 쓰이는 의미가 조금 다르다.
- 자료구조에서 동적 할당은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다.
- 반면 다이나믹 프로그래밍에서 다이나믹은 별 다른 의미가 없다. (🤔 띠용)
이미 계산된 결과는 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 한다.
👍🏻 다이나믹 프로그래밍의 조건
- 최적 부분 구조 (Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있다.
- 중복되는 부분 문제 (Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결한다.
ex) 피보나치 수열
- 피보나치 수열은 대표적인 DP 문제다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... - 인접한 항들 사이의 관계식인 '점화식'을 이용해서 수열을 표현하면 아래와 같다.
An = An-1 + An-2 ( a1=1, a2=1 )
앞에 있는 두 수의 합이 현재의 값으로 표현된다.
- f(4)를 구할 때, f(2)와 f(3)가 나누어져서 호출된다.
큰 문제를 작은 문제로 나눌 수 있으므로 최적 부분 구조 조건을 만족한다. - f(4)를 구할 때 f(2)와 f(3)이 호출되고, f(3)을 구할 때 f(1)과 f(2)가 호출된다.
이렇게 f(2)가 여러번 호출되는 것을 보아 중복되는 부분 문제 조건을 만족하는 것을 확인할 수 있다.
➣ 중복 부분 문제 조건을 보아 우리는 이미 해결해 놓은 문제를 다른 메모리 공간에 기록해놔야 한다 는 사실을 알 수 있다.
( 기록하지 않으면 매우 비효율적으로 계속 계산을 해야하기 때문~ )
📝 메모이제이션 (Memoization)
한번 계산한 결과를 메모리 공간에 메모하는 기법이다.
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
- 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
- top-down(하향식) 방식에서 사용한다.
- 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다.
⚠️ 따라서 한번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다. - 메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는
O(N)이다.
#메모이제이션을 위한 리스트 초기화
d = [0] * 100
#top-down 방식
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))🌠 top-down vs 🚀 bottom-up
-
top-down 방식은 하향식으로, 큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출한다.
그 작은 문제들이 해결되었을 때 큰 문제를 해결할 수 있도록 한다.
그 과정에서 한번 해결한 문제는 메모해두어서 그대로 가져오도록 한다. (메모이제이션) -
bottom-up 방식은 상향식으로, 작은 문제들을 하나씩 해결해나가면서 그 다음 문제를 해결해나가는 방식이다. 보통 반복문을 이용한다.
#메모이제이션을 위한 리스트 초기화
d = [0] * 100
#bottom-up 방식
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])다이나믹 프로그래밍 vs 분할 정복
-
다이나믹 프로그래밍과 분할정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
➣ 큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아서 큰 문제를 해결할 수 있기때문이다. -
두 방법의 차이점은 부분 문제의 중복이다.
⭐️ 다이나믹 프로그래밍만 각 부분의 문제들이 서로 영향을 미치면 부분 문제가 중복된다.
