Algorithm _#9 동적 계획법

동적 계획법

: 문제를 쪼개는데 divid & conquer와 달리 겹치게 쪼개도 됨 & 그렇게 푼 솔루션을 table에 저장 후 이를 조립

예시 1) Fibonacci number

• divide & conquer

  F(n):
      if n == 0 or n == 1:
      	return n
  	return F(n-1) + F(n-2)
  

  -> 중복하여 재귀 호출이 될 수 있음

• Dynamic programming

  F(n):
      F = [0,1] # F[0] = 0, F[1] = 1 (바닥조건)
      for i in range(2, n+1):
          F[i] = F[i-1]+F[i-2]
      return F #F0 ~Fn 모두 계산
  

  -> O(n)시간 내에 가능

예시 2) 계단 오르기

-> 1층에서 n층까지 오르는 경우의 수 계산

• A[n] = 1 -> n 오르는 경우의 수

• A[1] = 1, A[2] = 1, A[3] =2

• A[n] = (1 -> n-1)에 이르는 경우의 수(=A[n-1]) + (1 -> n - 2)경우의 수(=A[n-2])

  => A[n] = A[n-1] + A[n-2]

작은 문제의 솔루션부터 채워나가는 순서로!

최대구간합 문제

1. 단순한 방법

-> 다 더하기 : O(n^3)

for all i:
	for all j (>=i):
		S(ij) = A[i] + ...+ A[j]
		if max < S(ij):
			max = S(ij)

2. Prefixsum

P = []
P[0] = A[0]
n = len(A)
for i in range(1, n): # O(n)
    P[i] = P[i-1]+A[i]
    
for i in range(n):  #O(n^2)
    for j in range(i,n):
        S(ij) = A[i] + ... +A[j]

3. Divide & Conquer

=> O(nlogn)

max_interval(A,l,r):
	if l >= r:return A[l]
	m = (l+r)//2
	
	# 2*T(|A|/2)
	L = max_interval(A,l,m)
	R = max_interval(A,m+1,r)
	
	# O(|A|)
	# M 계산
	K = [0] * m
	K[0]= A[0]
	for i in range(1,m):
		K[i] = K[i-1] + A[i]
		if M < K[i]:
			M = K[i]

4. DP

1. 큰 문제 -> 작은 문제 분할 2. 큰 문제의 해 = 작은 문제 해의 점화식 3. DP 테이블(배열, 리스트) 순서대로 계산 4. 정확성 증명

# S[k] = A[k]로 끝나는 최대 구간 합
# S[k] = max(S[k-1] + A[k], A[k])
max_interval_DP(A):
	S = [0]*len(A)
	S[0] = A[0]
	for k in range(1, n):
		S[k] = max(S[k-1]+A[k], A[k])
	return max(S)

=> O(n)