카데인 알고리즘(Kadane's Algorithm) Python [알고리즘 이론]

 

 

 

 

 

 

학교 과제문제를 보고 고군분투하다가 알게 된 알고리즘입니다.

 

카데인 알고리즘(Kadane's Algorithm)은 주어진 배열 내에서 최대 연속 부분합(Subarray Sum)을 찾는 알고리즘입니다. 이 알고리즘은 동적 프로그래밍의 한 형태로 볼 수 있으며, 간단하면서도 효율적으로 문제를 해결할 수 있습니다. 음수와 양수가 혼합된 배열에서도 최대 연속 부분합을 O(n)의 시간 복잡도로 찾을 수 있습니다.

작동 원리

카데인 알고리즘의 기본 아이디어는 각 단계에서 "현재까지의 최대 부분합"과 "현재 원소를 포함한 최대 부분합"을 비교하는 것입니다. 이를 통해, 각 위치에서 끝나는 최대 부분합을 찾고, 이 중 최댓값을 최종 결과로 사용합니다.

알고리즘 절차

1. 초기화: 최대 부분합(max_sum)과 현재 부분합(current_sum)을 배열의 첫 번째 원소로 초기화합니다.
2. 반복 처리:
   • 배열을 순회하면서 각 원소를 현재 부분합에 더합니다.
   • 만약 current_sum이 음수가 되면, 현재 부분합을 다시 0으로 초기화합니다. 이는 음수 부분합이 더 큰 부분합을 만드는 데 도움이 되지 않기 때문입니다.
   • 각 단계에서 current_sum과 max_sum을 비교하여, max_sum을 업데이트합니다.
3. 결과 반환: 순회를 마친 후 max_sum을 반환합니다.

예시

예를 들어, 배열 [-2, 1, -3, 4, -1, 2, 1, -5, 4]가 주어졌을 때, 카데인 알고리즘을 사용하여 최대 연속 부분합을 찾는 과정은 다음과 같습니다:

• 초기화: max_sum = -2, current_sum = -2
• 첫 번째 원소(-2) 이후:
  • current_sum은 -2, max_sum은 -2
• 두 번째 원소(1):
  • current_sum = 1, max_sum = 1
• 세 번째 원소(-3):
  • current_sum = -2, max_sum = 1
• 네 번째 원소(4):
  • current_sum = 4, max_sum = 4
• ...
• 최종적으로, max_sum = 6이 되며, 이는 [4, -1, 2, 1] 부분 배열에 해당합니다.

특징

• 시간 복잡도: O(n)
• 공간 복잡도: O(1) (추가 공간을 거의 이용하지 않음)
• 음수와 양수가 혼합된 배열에서도 효율적으로 최대 부분합을 찾을 수 있음
• 단순하면서도 매우 강력한 알고리즘으로, 다양한 문제에서 응용될 수 있음

카데인 알고리즘은 최대 부분합 문제를 해결하는 가장 일반적인 방법 중 하나로, 알고리즘과 자료 구조를 공부하는 과정에서 반드시 이해하고 넘어가야 하는 중요한 알고리즘입니다.

 

 

 

아래는 python으로 작성한 카데인 알고리즘의 예시입니다.

def kadane_algorithm(nums):
    # 배열이 비어있는 경우
    if not nums:
        return 0

    # 최대 부분합과 현재 부분합을 배열의 첫 번째 원소로 초기화
    max_sum = current_sum = nums[0]

    # 배열의 두 번째 원소부터 순회 시작
    for num in nums[1:]:
        # 현재 원소를 포함한 최대 부분합을 계산
        # 현재 원소 자체와 현재 원소를 포함한 부분합 중 더 큰 값을 현재 부분합으로 선택
        current_sum = max(num, current_sum + num)
        # 최대 부분합 업데이트
        max_sum = max(max_sum, current_sum)

    return max_sum

# 예제 배열
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(kadane_algorithm(nums))

 

 

 

이 글은 생성형 AI 뤼튼을 이용하여 작성되었습니다!