6. Dynamic Programming(동적 계획법) ㅣ최대 구간 합 계산

Dynamic Programming (동적 계획법) ?

 Divide＆conquer(분할정복)와 유사하게, 문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법이다.

차이점은 큰 문제의 해답이 작은 문제의 해답들의 식으로 표현되는데, 그 답을 필요할 때마다 재귀적으로 얻는 것이 아니라, 분할된 문제의 해답을 기록해 놓은 후 재사용한다! → ★시간 단축에 매우 유리

---

 Fibonacci 수열로 차이점 알아보기

○ Divide＆conquer를 사용하는 피보나치 수열의 n번째 구하는 함수

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

 

※ F(4) 호출시, 함수 작동을 그림으로 표현 (n값에 따라 색줄 부여)

 

▷ 그림에서 볼 수 있듯이, 똑같은 함수를 여러번 호출하는 것을 볼 수 있다.

→ 매우 비효율적 (n이 커질 수록 시간소요가 급격히 증가한다.)

---

○ Dynamic Programming을 사용하는 피보나치 수열의 n번째 구하는 함수

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

▷ 리스트 F에 F[n-1]과 F[n-2]에 작은 문제 답을 미리 계산 후 저장하여 F[n] = F[n-1] + F[n-2] 로 F[n]을 저장

→ 리스트 F에 한번 for문이 작용하기 때문에 시간복잡도는 O(n)!

---

☆ Dynamic Programming 알고리즘의 4단계

1. 해답의 구조를 파악해 어떻게 부문제(subproblem)로 나눌 지 결정한다.
2. 부문제의 해답을 어떻게 조합해 더 큰 문제의 해답을 만들 수 있는지 식을 마련한다. → 보통 점화식으로 표현된다.
3. 작은 문제에서 큰 문제로 적당한 순서에 따라 해답을 계산하여 테이블에 저장하고 재사용하여 답을 계산한다.
4. 위의 단계들이 원래 문제의 답을 항상 출력함을 증명하고 답을 리턴한다.

---

최대 구간 합 계산 by Dynamic Programming

○ 최대 구간 합 계산 ?

▷ 정수 n 개 의 수열이 A [0], ..., A[n-1] 처럼 주어질 때, 이 수열에서 A[i] + A[i+1] + … + A[j]의 합이 최대가 되는

  연속된 인덱스 i , j (i <= j)를 계산하고, 그 최대 합을 구하는 알고리즘

 

○ 4단계 분석

 1. 부문제(subproblem)로 분할

▷ 최대합이 A[i] + … + A[j]이 라고 할 때, A[j]로 끝나는 구간 중에 최대합은 A[j] 혹은 A[j-1]로 끝나는

  최대 구간 합에 A[j]를 더 한 것일 수도 있다. 즉, 이 두 가지 경우 최대값을 취하면 된다.

 

▷ 하지만, 최대합이 어떤 A[j]에서 끝날지 모르기 때문에, 모든 j = 0, …, n-1까 지 모두 계산해보고

  그 중 최대합을 출력하면 된다.

 

 2. 부문제의 해답을 조합해 큰 문제의 해답으로 만들기

▷ A[0], …, A[i] 에 대해서, A[i]가 마지막에 포함되는 최대합을 S[i]라 하면,

  S[i]는 S[i-1] + A[i] 또는 A[i] 둘 중의 큰 값이 된다. S[i] = max( S[i-1]+A[i], A[i] )

 

 3. 테이블에 저장하기

▷ 테이블을 리스트 S로 표현하고, S[i]를 계산하기 위해선 S[i-1]을 알아야 하므로,

  i가 0, 1, …, n-1까 지 커지는 순서로 계산한다

 

 4. 답을 항상 출력함을 증명하기

▷ 답은 S의 가장 큰 값이므로 최대값을 리턴한다

---

○ 최대구간 합 코드

def max_interval(A) :
	S = [0]*len(A)
	S[0] = A[0]
	for i in range(1,len(A)) :
		S[i] = max(S[i-1]+A[i],A[i])
	return max(S)

 

○ 시간복잡도

▷ S의 원소 갯수 x 원소 값 하나 채우는 데 필요시간 

→ O (n) x O(1) = O(n)

 

○ 다른 방식으로 구하는 구간 합 계산의 시간복잡도

＊기초적인 방법 삼중 for문 방법 =O(n³)

＊prefix합을 이용한 방법 = O(n²) 

＊Divide＆conquer을 이용한 방법 = O(nlogn)

 

★ Dynamic Programming 알고리즘 사용으로 인한 엄청난 시간을 단축할 수 있음을 알 수 있다.

---

[출처]

신찬수 교수 (한국외국어대학교 컴퓨터 공학부), ‘알고리즘 - Algorithm with Python’, p.79~84

-Youtube : ‘Chan-Su Shin’

Chan-Su Shin