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

꼭 알아야 하는 25개 알고리즘에도 있다!

가장 큰 부분순열의 합을 구하는 문제는 "최대 부분 배열 합(Maximum Subarray Sum)" 문제로 알려진 유명한 문제다. 해결법으로 가장 유명한 알고리즘은 카데인 알고리즘(Kadane's Algorithm)이다. 카데인 알고리즘은 동적 프로그래밍을 활용하여, 배열을 한 번만 순회하면서 최대 부분 배열의 합을 효율적으로 찾는다. 이 알고리즘은 시간 복잡도 (O(n))을 가지며, 여기서 (n)은 배열의 크기다.

카데인 알고리즘의 기본 아이디어는 각 단계에서 현재까지의 최대 부분 배열 합을 계속 업데이트하는 것이다. 이때 두 가지 선택을 고려한다: 현재 원소를 포함하는 새로운 부분 배열을 시작하는 것이 더 나은지, 아니면 현재 원소를 이전 부분 배열에 추가하는 것이 더 나은지.

 

아래는 카데인 알고리즘을 구현한 파이썬 코드 예시입니다:

def max_subarray(numbers):
    """연속하는 하위 배열 중 가장 큰 합을 찾습니다."""
    best_sum = - float('infinity')  # 가장 큰 합을 -무한대로 초기화합니다.
    current_sum = 0  # 현재 합을 0으로 초기화합니다.
    for x in numbers:  # 주어진 숫자들에 대해 반복합니다.
        current_sum = max(x, current_sum + x)  # 현재 숫자와 현재 합에 현재 숫자를 더한 값 중 최대값을 현재 합으로 업데이트합니다.
        best_sum = max(best_sum, current_sum)  # 지금까지의 최대 부분 배열 합을 업데이트합니다.
    return best_sum  # 최대 부분 배열 합을 반환합니다.
    
    
import sys

def max_subarray_sum(arr:list)->int:
    max_sum = current_sum = arr[0]
    for num in arr[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
print(max_subarray_sum(arr))

이 코드는 다이나믹 프로그래밍(DP)의 개념을 사용하여 최대 부분 배열 문제를 해결합니다. 다음은 이 코드에서 DP의 사용을 설명한 것입니다:

1. current_sum 및 best_sum 변수: 이 코드에서는 current_sum 변수가 현재 위치에서 끝나는 최대 부분 배열의 합을 나타내며, best_sum 변수가 지금까지 발견한 최대 부분 배열의 합을 나타냅니다. 이러한 변수들은 부분 문제의 최적 솔루션을 계산하고 이를 다음 부분 문제에 사용하여 전체 문제의 최적 솔루션을 구하는 DP의 핵심 개념입니다.
2. 반복문: for x in numbers: 반복문은 입력 배열의 각 요소를 순회하면서 부분 문제의 최적 솔루션을 계산합니다. 각 요소에 대해 현재 합을 갱신하고 최대 부분 배열의 합을 업데이트하여 부분 문제의 최적 솔루션을 찾습니다.
3. 부분 문제 갱신: 각 요소 x에 대해 current_sum을 다음과 같이 업데이트합니다.이는 현재 요소 x를 포함하는 새로운 부분 배열의 합을 계산하고, 현재까지의 부분 배열 합과 비교하여 더 큰 값을 current_sum에 할당합니다. 이는 각 위치에서 끝나는 최대 부분 배열의 합을 계산하는 부분 문제를 해결합니다.
4. current_sum = max(x, current_sum + x)
5. 최종 결과 반환: 반복문이 종료되면 best_sum에는 주어진 배열에서 최대 부분 배열의 합이 포함되어 있습니다. 이 값을 반환하여 전체 문제의 최적 솔루션을 얻습니다.

https://youtu.be/4csAswCkXZM