동적계획법 예제1: 정수 리스트(배열)의 최대 부분합 구하기

다음과 같이 정수 리스트가 주어졌다고 합시다. 

[-2, -3, 4, -1, -2, 1, 5, -3]

이 때 연속된 부분 리스트의 합 가운데 최대 값은 어떻게 구해야 할까요?

 

가장 먼저 생각해볼 수 있는 방법은 모든 부분배열을 만들어 그 합을 구한 뒤 가장 큰 값을 구하는 것이 되겠습니다.

def maximum_sub_sum_bruteforce(data):
    max_sub_sum = int()
    for e in data:
        if e < 0:
            max_sub_sum += e
    for i in range(len(data)):
        for j in range(i, len(data)):
            sub_sum = sum(data[i:j + 1])
            if sub_sum > max_sub_sum:
                max_sub_sum = sub_sum
    return max_sub_sum


d = [-2, -3, 4, -1, -2, 1, 5, -3]
print(maximum_sub_sum_bruteforce(d))

먼저 리스트의 음의 정수만 더해서 리스트 내에서 만들어 낼 수 있는 최소 값보다 작은 값을 만들고 이를 최대값으로 초기화 합니다.

그 후 각각의 부분 리스트에 대한 합을 최소 값과 비교하여 그 보다 큰 경우에만 최대값을 업데이트 합니다.

모든 부분 리스트를 확인한 뒤 마지막에 남은 최대값이 찾고자 하는 답이 됩니다.

하지만 위의 알고리즘은 O(n^3) 시간 복잡도를 보여줍니다. 개선의 여지가 있습니다.

 

 

동적계획법을 통해 시간 복잡도를 줄여보도록 합시다.

먼저 주어진 리스트의 첫번째 원소를 취하고 이를 현재까지의 최대 부분합이라고 가정합니다.

두번 째 원소와 최대 부분합을 더한 값과 두번 째 원소 중 더 큰 값이 최대 부분합이 됩니다.

(즉, [-1, 3] 이라고 리스트가 주어지면 최초의 최대 부분합은 -1이지만 두번째 리스트까지의 최대합은 -1 + 3과 3 중 더 큰 값이 된다는 것입니다.)

위의 과정을 주어진 리스트의 마지막까지 반복하면 최대 부분합을 얻을 수 있습니다.

def maximum_sub_sum(data):
    length = len(data)
    dp_table = [0] * length
    dp_table[0] = data[0]
    for i in range(1, length):
        dp_table[i] = max(dp_table[i - 1] + data[i], data[i])
    return max(dp_table)


d = [-2, -3, 4, -1, -2, 1, 5, -3]
print(maximum_sub_sum(d))

위와 같이 동적계획법을 사용하여 시간복잡도를 O(n^3)에서 O(n)으로 개선할 수 있습니다.