[Algorithm] 동적 프로그래밍 Dynamic Programming

🗝️동적 프로그래밍

복잡한 문제를 간단한 부분 문제로 분할하여 부분해를 찾은 후, '기록'하는 과정을 반복하여 모든 부분해들을 찾고, 원래 문제의 해결책을 찾는 전략이다.

• 한번 해결된 부분 문제의 정답을 메모리에 기록하여, 한번 계산한 답은 다시 계산하지 않도록 하는 문제해결 기법

• 'programming'의 의미는 과정이 테이블에 기록되는 것을 뜻하며, 'dynamic'의 의미는, 테이블이 갱신되는 것을 뜻한다.

---

⬆️ 상향식 방식 ⬆️

동적 프로그래밍은 주어진 문제를 분할한 후 더 작은 부분 문제의 해를 찾은 후, 이를 통합하여 더 큰 문제의 해를 찾는 상향식 문제해결 전략이다.

• 따라서 부분 문제들의 해를 기록하여 완벽히 동일한 부분 문제의 해를 다시 찾아야 할 경우, 저장된 해를 재사용한다.

---

🔉피보나치 수열

• 피보나치 문제는 다이나믹 프로그래밍으로 해결 가능한 대표적 예시이다.

• n번째 피보나치수를 찾는 문제를 아래와 같이 풀이할 경우, 완벽히 동일한 문제가 중복된다. 이러한 중복을 피할 수 있다면 수행시간을 줄일 수 있다.

def fibo(n):
	 if n == 0 or n == 1:
     	return n
     return fibo(n-1) + fibo(n-2)
     
print(fibo(5))

• 따라서 아래와 같이 한번 계산한 i번째 피보나치 수를 모두 리스트에 저장해둔 후, 나중에 i번째 피보나치를 구할 때 이전에 계산한 값을 반환한다.

def fibo_dp(n) :
	cache = [0 for _ in range(n+1)]
    cache[0] = 0
    cache[1] = 1
    for i in range(2, n+1):
    	cache[i] = cache[i-1]+cache[i-2]
    return cache[n]