11. 다이나믹 프로그래밍-1

2021-08-05

2022-01-23

다이나믹 프로그래밍

문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법.

divde and conquer와 차이점은?

큰 문제의 답이 작은 문제의 답들의 식으로 표현되지만,
그 답을 얻을 때 재귀적으로 얻는게 아니라 미리 계산하여 기록해 놓은 값을 재귀 식에 따라 계산!

즉 원래 문제의 답을 작은 문제들의 재귀 식으로 표현하는 것이 핵심!!!!

점화식을 찾아내고, 점화식에 필요한 값들만 중복 없이 리스트에 저장하여 문제를 해결하는 게 중요!

예를 들면, 계단 오르기 문제.

한번에 계단을 하나 혹은 두개씩 오른다고 할 때
n번째 계단에 오는 경우의 수는?

k번째 계단에 오는 경우의 수 = k-1번째 계단에 오는 경우의 수 + k-2번째 계단에 오는 경의의 수 이다. (k-1에서 한칸 오르거나 ,k-2에서 두칸 오르는 것의 합)
즉 T(k) = T(k-1)+T(k-2)인 점화식이 완성된다.

T(1) = 1, T(2) = 2이므로, 이들을 리스트에 넣고, T(3) = 3 을 구한 다음,
T(2), T(3)을 리스트에 기록 후, T(4) = 6을 구하고…

이런 식으로 T(n)까지 구해가는 게 다이나믹 프로그래밍이다!

최대 구간 합 문제

랜덤한 n개의 수를 가진 배열이 주어지고, 이 배열에서 연속된 수의 합이 최대값을 구하라.

divide & conquer

배열을 반으로 잘라서, 왼쪽, 오른쪽 혹은 가운데에서 최대값을 구함.

def max_interval(A, l, r):
    if l >= r : return A[l]
    m = (l+r)//2
    L = max_interval(A, l, m)
    R = max_interval(A, m+1, r)
    #가운데 최대값 구하기
    bigLeft =0
    sumLeft =0
    sumRight=0
    bigRight=0
    for i in range(m, l-1,-1):
        sumLeft+=A[i]
        if(sumLeft>bigLeft):
            bigLeft=sumLeft
    for j in range(m+1, r+1, 1):
        sumRight+=A[j]
        if(sumRight>bigRight):
            bigRight=sumRight
    M = bigRight+bigLeft
    return max(L, M, R)

이 방식은 T(n) = 2T(n/2)+ cn 이므로 ,O(n log n)

다이나믹 프로그래밍으로 풀기

일단 다이나믹 프로그래밍을 풀기 위해 4가지 단계를 기억하자.

큰 문제를 작은 문제로 분할한다.(해를 분석하라는 의미!)
큰 문제의 해가 작은 문제 해 점화식으로 표현
dp테이블에 작은 문제의 해를 차근차근 저장
정확성을 증명.

===

이 네가지 단계로 최대 구간 합 문제를 풀어보자

A[k]로 끝나는 최대 구간의 값은? A[k] + A[k-1]로 끝나는 최대구간합!!
즉 T(k) = T(k-1)+A[k]

이제 dp테이블 S에 해를 저장해보자.
S[k] = max(S[k-1]+A[k], A[k])이고,
S[0] = A[0]

def 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) 밖에 안된다!

mudura

Computer ScienceAlgorithmTheory