배열에서 연속된 요소들의 합이 가장 큰 구간을 찾는 최대 하위 배열(Maximum Subarray) 문제는 알고리즘 학습에서 자주 등장하는 대표적인 문제입니다. 이 글에서는 분할 정복(Divide and Conquer) 기법을 활용해 이 문제를 해결하는 Python 프로그램을 소개합니다.
분할 정복 방식은 배열을 두 개의 절반으로 나눈 뒤, 왼쪽 절반의 최대 합, 오른쪽 절반의 최대 합, 그리고 중간을 가로지르는 구간의 최대 합 세 가지를 각각 계산하고, 그중 가장 큰 값을 반환하는 방식으로 동작합니다.
예제 코드
def max_crossing_sum(my_array, low, mid, high):
sum_elements = 0
sum_left_elements = -10000
for i in range(mid, low-1, -1):
sum_elements = sum_elements + my_array[i]
if (sum_elements > sum_left_elements):
sum_left_elements = sum_elements
sum_elements = 0
sum_right_elements = -1000
for i in range(mid + 1, high + 1):
sum_elements = sum_elements + my_array[i]
if (sum_elements > sum_right_elements):
sum_right_elements = sum_elements
return max(sum_left_elements + sum_right_elements, sum_left_elements, sum_right_elements)
def max_sub_array_sum(my_array, low, high):
if (low == high):
return my_array[low]
mid = (low + high) // 2
return max(max_sub_array_sum(my_array, low, mid), max_sub_array_sum(my_array, mid+1, high), max_crossing_sum(my_array, low, mid, high))
my_list = [23, 12, 45, 67, 89, 11]
list_length = len(my_list)
print("The list is :")
print(my_list)
max_sum = max_sub_array_sum(my_list, 0, list_length-1)
print("The maximum contiguous sum is ")
print(max_sum)실행 결과
The list is : [23, 12, 45, 67, 89, 11] The maximum contiguous sum is 247
코드 설명
max_crossing_sum함수는 중간 지점을 기준으로 왼쪽과 오른쪽에 걸친 구간의 최대 합을 계산합니다. 먼저 중간부터 시작점까지 거꾸로 탐색하며 왼쪽 부분의 최대 누적 합을 구하고, 이어서 중간 다음 위치부터 끝까지 순방향으로 탐색하며 오른쪽 부분의 최대 누적 합을 구한 뒤 두 값을 더해 반환합니다.max_sub_array_sum함수는 재귀적으로 호출되며, 배열을 계속 반으로 나눠(mid = (low + high) // 2) 왼쪽 절반의 최대 합, 오른쪽 절반의 최대 합, 그리고 중앙을 가로지르는 최대 합 세 값 중 가장 큰 값을 반환합니다. 분할된 구간의 크기가 1이 되면 해당 요소를 그대로 반환하며 재귀가 종료됩니다.함수 외부에서는 예시 리스트
my_list를 정의하고 콘솔에 출력합니다.len()함수로 리스트의 길이를 구한 뒤, 이를 인자로 전달하여 최대 하위 배열 합을 계산하는 함수를 호출합니다.최종적으로 계산된 최대 연속 구간 합인 247(리스트 전체 요소의 합)이 콘솔에 출력됩니다.
시간 복잡도
이 분할 정복 접근법의 시간 복잡도는 O(n log n)입니다. 매번 배열을 절반씩 나누는 과정이 log n번 발생하고, 각 단계에서 중앙을 가로지르는 합을 계산하는 데 O(n)의 시간이 걸리기 때문입니다. 참고로 카데인(Kadane) 알고리즘을 사용하면 O(n)의 시간 복잡도로 같은 문제를 해결할 수 있습니다.