[PS|DP] 부분배열과 부분집합의 구현

백준에는 잘 나오지 않는 부분 배열/부분 집합 DP 로직에 대해 정리해 보았다.
1차원 배열 A에서 생각해볼 수 있는 DP 접근을 다양하게 해볼 수 있다.

간단한 목차는 아래와 같다.
1. 배열 A의 부분 배열의 최댓값 (제한 X)
2. 배열 A의 k개의 연속한 부분 배열의 최댓값 (k개라는 제한이 존재한다)
3. 배열 A의 k개 이상 연속한 부분 배열의 최댓값 (k개 이상이라는 제한이 존재한다.)
4. 배열 A에서 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부, 제한 X)
5. 배열 A에서 k개의 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부, k개라는 제한이 존재한다)

---

1. 배열 A의 부분 배열의 최댓값 (제한 X)

배열 A가 주어졌을 때, 이 배열의 부분 배열 A의 최댓값을 구하라. 이 때 배열 속 원소가 양의 정수, 0, 음의 정수가 모두 가능하다.

arr=list(map(int,input().split()))
dp=[0]*len(arr)
dp[0]=arr[0]
for i in range(1, len(arr)):
    dp[i]=max(0, dp[i-1]+arr[i])
print(max(dp))

부분 배열은 아무것도 선택하지 않는 것도 포함한다.
즉 배열 A가 -1,-3,-5,-9 이런식으로 되어 있을 때 답은 0이다. 이를 고려하면 위와 같은 코드가 나옴을 알 수 있다.
따라서 위의 코드 dp[i]=max(0, dp[i-1]+arr[i]) 에서 dp[i]에서 볼 수 있듯
앞에 더한 것에 포함시켜 현재 수를 더하거나, 아예 아무 일도 하지 않는 (아무것도 포함시키지 않는) 로직 두 개로 이분법적으로 결정할 수 있다. 
이후 최대 값은 해당 dp에서의 max값이다. 
이해가 안된다면 하나씩 손으로 써보는 것 추천..!

---

2. 배열 A의 k개의 연속한 부분 배열의 최댓값 (k개라는 제한이 존재한다)

def max_subarray_sum_k(A, k):
    n = len(A)
    dp = [0] * n
    current_sum = sum(A[:k]) #일단 0에서 k개까지의 합

    for i in range(k, n):
        current_sum += A[i] - A[i-k]
        dp[i] = current_sum

    return max(dp)


print(max_subarray_sum_k([1,5,6,3,-1,5,6],3))

말만 어렵지 쉬운 구현을 요한다.
dp에 k개를 연속한 수들의 최대값들을 메모이제이션한다.
이를 위해 index k부터는 뒤에꺼 하나 빼고 앞에 꺼 하나 더 한 것들을 DP에 저장한다.
이후 DP의 max값이 최대값이다!

---

3. 배열 A의 k개 이상 연속한 부분 배열의 최댓값 (k개 이상이라는 제한이 존재한다.)

해당 로직은 위의 1&2번을 섞어서 구현하면 된다.
 

def max_subarray_sum_k_or_more(A, k):
    n = len(A)
    max_k_dp = [0] * n
    current_sum = sum(A[:k]) #일단 0에서 k개까지의 합
    max_sum = 0

    for i in range(k, n):
        current_sum += A[i] - A[i-k]
        max_k_dp[i] = current_sum

    dp=[0]*len(A)
    dp[0]=A[0]
    for i in range(1, len(A)):
        dp[i]=max(0, dp[i-1]+A[i])

    for i in range(k, n):
        max_sum = max(max_sum, dp[i]+max_k_dp[i-3])

    return max_sum
print(max_subarray_sum_k_or_more([-2,-3,4,-1,-2,1,5,-3],3))

즉 'k개만'이라는 제한을 둔 max_k_dp가 있고, 제한이 없는 dp가 있다고 하면 "최소 k개 이상 연속한 값의 합 중 최대"는 이 둘의 로직을 모두 적용시켜 max_dp[i]=max_k_dp[i-3]+dp[i] 이다. 
잘 생각해보면 'k개만' 도 흐트러뜨리지 않고 k개를 넘은 수도 적용시킨다.

---

4. 배열 A에서 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부)

※ 4,5번은 위의 것과는 조금 다르다 ※
부분집합과 부분배열은 다른 개념이다! 그것부터 주의하자. 여기에서는 부분집합의 합이 k인 부분집합의 존재여부만을 판단하려고 한다.

def subset_sum(nums, target):
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    # dp[i][j] : i개 이하의 숫자를 가지고 합이 j가 되게 할 수 있다면 True
    # init 
    for i in range(n + 1):
        dp[i][0] = True
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if j < nums[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
    
    print(dp)
    return dp[n][target]


nums = [3, 34, 4, 12, 5, 2]
S = 9
is_possible = subset_sum(nums, S)
print(f"부분집합의 합이 {S}인 부분집합이 존재하는가? {is_possible}")

부분집합의 핵심은 '현재 위치의 것을 넣어도 되고 안 넣어도 된다'이다. 따라서 DP를 2차원으로 구현해야 한다.

1. DP[i][j]는 i개 이하의 숫자를 가지고 합이 j가 되게 할 수 있다면 True
로 해석해볼 수 있다.
이후 위의 손그림처럼 하나씩 DP table을 할당하여 dp[n][target], 즉 가장 오른쪽 아래가 True인지를 판단하면 된다.
해당 로직의 실행시간은 O(nk)이다.

---

4. 배열 A에서 k개로 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부)

def subset_sum_exists(A, k, S):
    n = len(A)

    if S == 0 and k == 0:
        return True

    if S != 0 and k == 0:
        return False

    dp = [[0] * (S + 1) for _ in range(k + 1)]
    # DP[i][j]: 정확히 i개의 숫자를 가지고 합이 j가 되게 할 수 있다면 True

    dp[0][0] = 1

    for j in A:
        if j <= S and j>0: #이 때 j가 음수일 때 주의
            dp[1][j] = 1

    for i in range(2, k + 1):
        for j in range(1, S + 1):
            for a in A:
                if j-a<=S and a<=S:
                    if dp[i-1][j-a] == 1 and dp[1][a] == 1:
                        dp[i][j] = 1
                        break
    print(dp)                    
    return dp[k][S] == 1

print(subset_sum_exists([-2, -3, 4, -1, -2, 1, 5, -3],2,11))

DP[i][j]는 정확히 i개의 숫자를 가지고 합이 j가 되게 할 수 있다면 True
로 구현해볼 수도 있다.
이 때는 
#init
만약 j가 A에 들어있고 양수라면 DP[1][j]=1로 초기화

DP[i-1][j-a]=1이고 DP[1][a]=1인 a가 1~target 사이에 있다면 DP[i][j]를 1로 할당시킨다. (bruteforce)
이 로직의 실행시간은 O(nkS)이다.