카데인(Kadane) 알고리즘은 주어진 숫자 배열에서 연속된 요소들의 합이 가장 큰 최대 부분 배열(maximum subarray)을 찾는 대표적인 동적 계획법 기반 알고리즘입니다. 이 글에서는 카데인 알고리즘을 활용해 최대 부분 배열을 찾는 함수를 정의하고, 반복자(iterator)를 통해 최대 부분 배열의 시작 인덱스, 끝 인덱스, 그리고 합계를 추적하는 방법을 살펴봅니다.
예제 코드
다음은 카데인 알고리즘을 구현한 파이썬 코드입니다.
def find_max_sub_array(my_list, beg, end):
max_end_at_i = max_seen_till_now = my_list[beg]
max_left_at_i = max_left_till_now = beg
max_right_till_now = beg + 1
for i in range(beg + 1, end):
if max_end_at_i > 0:
max_end_at_i += my_list[i]
else:
max_end_at_i = my_list[i]
max_left_at_i = i
if max_end_at_i > max_seen_till_now:
max_seen_till_now = max_end_at_i
max_left_till_now = max_left_at_i
max_right_till_now = i + 1
return max_left_till_now, max_right_till_now, max_seen_till_now
my_list = input('Enter the list of numbers... ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
beg, end, max_val = find_max_sub_array(my_list, 0, len(my_list))
print('The maximum subarray begins at index {}, ends at index {}'
' and its sum is {}.'.format(beg, end - 1, max_val))실행 결과
Enter the list of numbers... 2 5 7 12 6 8 The maximum subarray begins at index 0, ends at index 5 and its sum is 40.
코드 설명
find_max_sub_array라는 이름의 함수가 정의되며, 리스트와 탐색 범위의 시작·끝 인덱스 등 세 개의 매개변수를 받습니다.함수는 주어진 범위 내에서 합이 가장 큰 부분 배열을 찾습니다.
결과로는 최대 부분 배열의 왼쪽 인덱스, 오른쪽 인덱스, 그리고 합계를 담은 튜플(tuple)을 반환합니다.
루프를 돌면서 인덱스 i에서 끝나는 부분 배열의 최대합(
max_end_at_i)을 갱신합니다. 이전까지의 합이 양수라면 현재 값을 더하고, 음수라면 새로 시작하는 것이 유리하므로 현재 값으로 초기화합니다.동시에 지금까지 확인한 모든 부분 배열 중 최댓값(
max_seen_till_now)과 그때의 왼쪽·오른쪽 인덱스도 함께 기록합니다.함수 외부에서는 사용자로부터 숫자 목록을 입력받아 공백 기준으로 분리한 뒤 정수 리스트로 변환합니다.
변환된 리스트가 함수의 매개변수로 전달되며, 최종 결과는 콘솔에 출력됩니다.
시간 복잡도
카데인 알고리즘은 배열을 한 번만 순회하면 되기 때문에 시간 복잡도는 O(n)입니다. 모든 가능한 부분 배열을 일일이 검사하는 브루트 포스 방식(O(n²) 또는 O(n³))에 비해 훨씬 효율적이므로, 코딩 테스트와 실무에서 널리 활용됩니다.