Max Array Sum

def maxSubsetSum(arr):
    if len(arr) == 1:
        return arr[0]
        
    dp = [arr[0], max(arr[:2])] + [0]*(len(arr)-2)
    for i in range(2, len(arr)):
        dp[i] = max(arr[i], dp[i-1], dp[i-2]+arr[i])
    
    return dp[-1]

인접하지 않은 부분집합의 합 중 제일 큰 합을 출력하는 문제였다.

먼저 시간 복잡도를 생각하지 않고 구현하면, 1) 모든 부분집합을 구하고 2) 부분집합 중 인접하지 않게 필터링하고 3) 남은 부분집합 중의 합을 구한다. 물론 시간 복잡도가 넘어간다.

 

다이나믹 프로그래밍을 이용해서 풀어보자.

Dynamic programming은 Divide and conquer와 혼동할 수도 있는데, 핵심은 전에 해결한 값을 이용해서 다음 값을 구한다는 것이다.

즉, DP(Dynamic programming)와 DC(Divide and conquer)의 차이점은 종속이냐 아니면 병렬이냐로 나눌 수 있다. 전에 구한 해가 다음 해에 영향을 끼치면 ? DP 아니면 DC

 

임의의 Input 값을 만든다.

[2 1 5 8 4]

각 원소의 인덱스에서의 최적해를 구한다. 이 문제에서의 최적해란 누적합이다.

dp[0]의 최적해는 2, dp[1]의 최적해는 2다(2,1 중 더 큰 수).

dp[2]는 몇이 될까? 3개의 후보군이 있다.

 

1. 자기 자신: 5
2. 자기 자신 + 2 (dp[0]): 7
3. 바로 앞의 최적해: 2 (dp[1])

 

첫번째와 두번째 경우의 수는 생각하기 쉽지만 마지막 경우의 수를 놓칠 수 있다. 자기 자신의 숫자가 음수라고 가정하면 첫번째, 두번째 경우의 수가 음수가 될 수 있다. 그럴 경우 앞의 최적해가 더 높은 수가 되는 경우가 있기 때문에 이때는 해당 최적해를 선택하게 되는 것이다.

위에서 뽑아낸 경우의 수는 재귀적인 구조로 정의 된다. 정의된 구조를 코드로 옮기기만 하면 문제를 해결할 수 있다.

 

다이나믹 프로그래밍은 이름만 들으면 어렵지만 문제를 차근차근히 생각하면 재귀식을 뽑아낼 수 있다.