큰 문제를 작은 문제로 나누고, 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법론
f(n-2) + f(n-1) = f(n)- 피보나치 수열 알고리즘은 재귀 함수 알고리즘을 활용
- 항이 커져갈수록 굉장히 많은 중복 호출이 발생한다는 문제점 발생
- 재귀 : 자기 자신을 호출하는 함수
어떤 경우에서 활용할 수 있을까?
DP를 사용하기 위해서는 아래 두 가지의 조건이 만족되어야 함
- 최적 부분 구조 (Optical Substructure)
- 작은 문제들의 최적의 답을 이용해 큰 문제의 최적의 답을 구할 수 있어야 함
- 즉, 큰 문제의 답에 작은 문제의 답이 포함되어 있음
- 부분 문제 반복 (Overlapping Subproblem)
- 작은 문제의 답을 재활용하기 때문에 동일한 부분 문제가 반복적으로 나타나야함
- 즉, 한 번 구한 답이 다음에 반복됨
"컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거해 프로그램의 실행속도를 빠르게 하는 기술"
- 동적 계획법의 핵심 개념
- 기억하며 풀기
- 작은 문제의 답을 메모하여 다음에 재사용하는 기법
- 따라서 모든 작은 문제들은 단 한 번만 풀이되며, 이 답을 기억해야함
- Bottom-Up
- 작은 문제부터 차근 차근 해결해 큰 문제를 해결하는 방법
- For문 활용
- 재귀호출이 없어 시간과 메모리 절약 가능
- But, 직관적 이해 힘듦
memo = [0]*100
for i in range(0, n):
if i<2:
memo[i] = i+1
else :
memo[i] = memo[i-1] + memo[i-2]- Top-Down
- 큰 문제부터 시작해 작은 문제로 쪼개며 문제를 해결하는 방법
- 재귀 활용
- 이전 계산 값이 있으면 쓰고 없으면 계산
- 점화식 이해 쉬움
- 최대 재귀 깊이 초과 에러 발생 가능
memo = [0]*100
# Idx 1부터라고 가정
def topDown(n):
if n<=2:
return n
if memo[n] != 0 :
return memo[n]
memo[n] = topDown(n-1) + topDown (n-2)
return memo[n]각 방법은 어떨 때 유용할까?
Top-Down : 하위 문제가 복잡할 경우
Bottom-Up : 효율성을 고려할 경우
[참고 자료]