[Algorithm] 동적계획법(Dynamic programming) - Brute Force, Kadane’s Algorithm

#동적계획법(Dynamic programming) 

 - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 (wikipedia)

 - Bottom-Up 적 방법

 

 

#동적계획법 예제 - nm선 자르기

#nm의 선을 1m나 2m 자르는 방법의 수

#1m 선의 경우
#[1,1,1] => 1가지
#dy[1]=1

#2m 선의 경우
#[1,1,1],[2] => 2가지
#dy[2]=2

#3m 선의 경우
#[1,1,1] => 1가지
#[1,1,1],[2] => 2가지
#1가지(1m선의 경우) + 2가지(2m선의 경우)  = 3가지
#dy[3]=3

#4m 선의 경우
#2가지(2m선의 경우) + 3가지(3m선의 경우)  = 5가지
#dy[4]=5

n = int(input())
dy=[0]*(n+1) #배열을 만듦
dy[1]=1
dy[2]=2

for i in range(3, n+1): #3부터 n+1 범위 계산
    dy[i] = dy[i-1]+dy[i-2]

print(dy[n])

 

#Brute Force 접근법

: 가능한 부분 배열들을 모두 살펴본 후 합을 구해서 가장 큰 값을 찾는 방식

 

 

#카데인 알고리즘 (Kadane’s Algorithm)

: A[0]이 아닌 A[n-1]에서(뒤에서 부터) 시작하는 방식

 

 

#카데인 알고리즘 (Kadane’s Algorithm) 예제 - Maximum Subarray Problem(최대 부분 합 구하기)

 

 

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

(출처 :  https://sustainable-dev.tistory.com/23)

 

 

A[5]의 최대 부분합 = A[4]의 최대 부분합+A[5] = 3+2 = 5

A[6]의 최대 부분합 = A[5]의 최대 부분합+A[6] = 5+1 = 6

A[7]의 최대 부분합 = A[6]의 최대 부분합+A[7] = 5-5 = 0

A[8]의 최대 부분합 = A[7]의 최대 부분합+A[8] = 0+4 = 4

 

localMaximum[i] = max(A[i], A[i] + lacalMaximum[i-1])
#i번째에서는 A의 i번째 수와 i-1번째의 최대 부분합을 더한다.