[Baekjoon]백준 1912 연속합(실버 2) - Python # 카데인 알고리즘

문제설명

예제

문제만 살펴보면 꽤나 간단한 문제이다 연속합을 구한 후에 그 중에서 가장 큰 값을 출력하면 된다

그래서 비효율적인것도 알고 시간 초과가 발생할 거 같다는 생각이 당연히 들었지만

일단 한 번 시도해보기로 하고 코드를 작성하였다

make_sum 함수를 통해 n개의 연속적인 값을 더하는 함수를 만들었고, 그 중에서 최댓값을 return하도록 하였다

이후 n개의 return한 값들 중에서 최댓값을 출력하는 로직을 구현하였다

def make_sum(ls, n):
    sm = []
    ls_sum = 0
    for i in range(len(ls) - n + 1):
        for j in range(n):
            ls_sum += ls[i + j]
        sm.append(ls_sum)
        ls_sum = 0
    return max(sm)

n = int(input())
n_ls = list(map(int, input().split()))
sum_ls = []

for i in range(1, n + 1):
    res = make_sum(n_ls, i)
    sum_ls.append(res)
    
print(max(sum_ls))

결과는..예상대로 시간초과였다

이후 동적계획법을 활용하여 어떻게 풀어야할지 고민해보다가 카데인 알고리즘이라는 것을 알게되었다

위의 코드는 Brute Force알고리즘이기 때문에 시간 복잡도가 O(N^2)인것에 비해 

카데인 알고리즘의 시간 복잡도는 O(N)이다 카데인 알고리즘의 핵심은 각 index의 최대 부분합은

이전 index의 최대 부분합이 반영된 결과값이라는 것이다

 

이해하기 쉽도록 예시를 통해 설명해보겠다

n = 5이고 x = [-2, 1, -3, 4, -1]라는 경우가 존재한다고 가정하자

카데인 알고리즘인 

for i in range(1, n):
    n_ls[i] = max(n_ls[i], n_ls[i] + n_ls[i-1])

을 통해 구해보면, [-2, 1, -2, 4, 3]이 결과값으로 나오게된다

i가 1일때 -2와 1을 더하게 되면 -1이 나온다 그러나 i가 1일때의 값은 1이기 때문에 기존 위치의 값이 더 크기 때문에

n_ls[1]의 값은 그대로 1이 된다 이 말인 즉슨, i가 1일때의 최대 부분합은 1이라는 뜻이다

 

이제 i가 2일때를 가정해보자

n_ls[2]는 -3이고, 이전 값은 1이다 이 둘을 더하였을 때 더 큰 값은 -3과 1을 더한 -2가 될 것이다

이는 i가 2일때 가질 수 있는 최대 부분합이 -2라는 뜻이 된다

이러한 과정을 계속해서 반복하는 것이 카데인 알고리즘이다

각 위치에서 얻을 수 있는 최대 부분합을 계속해서 구해가며 값을 갱신하게 되며, 이를 통해 우리는 최대값을 찾을 수 있다

n = int(input())
n_ls = list(map(int, input().split()))

for i in range(1, n):
    n_ls[i] = max(n_ls[i], n_ls[i] + n_ls[i-1])
print(max(n_ls))