[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming, DP)

• 여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
• 문제를 해결하기 위한 점화식을 먼저 찾아낸 후, 점화식의 항을 밑에서부터 차례로 구해나가면서 답을 알아내는 알고리즘
• 풀이 과정
  • 테이블 정의하기
  • 점화식 찾기
  • 초기값 정하기

---

📕 문제 1. 피보나치 수열

• 재귀에서의 피보나치 수열은 중복된 연산이 계속 발생.
• e.g. fibo(5) = fibo(4) + fibo(3) = fibo(3) + fibo(2) + fibo(3) = ...
• 이미 구했던 값을 계속 연산하기 때문에 O(1.1618^N)의 시간복잡도를 가짐

def fibo(n):
	if n <= 1: return 1
	return fibo(n-1) + fibo(n-2)

• 피보나치 수열 문제를 DP로도 해결할 수 있음.
• 미리 배열을 만들어두고 인덱스를 채워나가는 방식으로 해결 가능
• 시간복잡도 O(N)

def fibo(n):
	arr = [0] * 20
    arr[0] = arr[1] = 1
    for i in range(2, n+1):
    	arr[i] = arr[i-1] + arr[i-2]
	return arr[n]

---

💻 연습 문제

바킹독 - 다이나믹 프로그래밍 문제집

---

ℹ️ 참고

바킹독 - 다이나믹 프로그래밍