Maximum Subarray Problem
Maximum Contiguous Subsequence은 가장 큰 연속적인 배열의 합을 구하는 문제이다.
예를 들어 다음과 같은 14개의 정수가 주어졌을 때,
[4, -6, 0, 2, 3, -4, 1, 3, 0, -9, 4, 1, -3, 2]
이 배열에서 가장 큰 합을 가지는 연속적인 서브 배열은 [2, 4], [2, 7], [2, 8], [3, 4], [3, 7], [3, 8], [10, 11] 등으로 최대합은 5이다.
문제 마다 요구하는 출력조건은 다르지만, 이번에는 구간 시작 정수가 0이 아니고 index가 가장 작은 경우만 출력하고 만약 시작 index가 가장 작은 경우가 여러개라면 그중에서 가장 짧은 구간을 가지는 구간을 출력하도록 하겠다.
이 문제를 해결하는 방법은 주먹구구 방식인 Brute Force와 Kadane 알고리즘 두가지가 있다.
Brute Force 알고리즘
Brute Force 방법은 말 그대로 모든 서브 배열의 합을 다 구한 후 최댓값을 찾는 방식이다.
예를 들어 아래의 그림처럼 인덱스가 0부터 시작해서 0에서 시작하는 모든 서브 배열의 합을 계산한다. 그다음 인덱스 1에서 시작하는 모든 서브 배열의 합을 계산한다. 이렇게 0부터 ....... n-1까지 시작하는 모든 서브 배열의 합을 차례대로 구한다.
이렇게 구한 모든 서브 배열의 합 중 가장 큰 값을 고르고 그 구간을 출력한다.
이하지만 이런 방식은 배열이 커지면 복잡도가 급격하게 올라간다. 예를 들어 배열의 크기가 n이라고 한다면 O(n^2)로 좋은 풀이 방법이 아니다.
분할 정복으로 해결
위의 방법에서 조금 더 나아가서 Divide & Conquer로 해결할 수 있는 방법이 있다.
Divide : n 개의 정수배열을 크기가 각각 n/2개인 부분 배열로 나눈다.
Conquer : 크기가 각각 n/2개인 부분 배열에 대하여 recursive하게 문제를 해결한다.
Combine : Conquer 단계에서 계산한 값과 다음 과 같이 연속된 구간이 중앙을 걸쳐서 존재할 수도 있으므로 이런 경우도 해결해야한다. 이를 위해서는 중앙을 중심으로 왼쪽으로 연속적으로 최대학 되는 값과 중앙을 중심으로 오른쪽으로 연속적으로 최대가 되는 값을 구하여 합한다.
따라서, 전체 데이터중에서 최대의 합을 만드는 연속적인 구간은 다음 세 값 중의 하나다.
- 왼쪽 n/2 데이터에서 최대 연속구간의 합.
- 오른쪽 n/2 데이터에서 최대연속구간의 합.
- 중앙에 걸쳐서 최대연속 구간의 합.
이 알고리즘은 combine단계에서 중앙을 거쳐서 최대가 되는 연속구간을 계산하는데 걸리는 basic operation은 n-1번 수행되기 때문에 시간복잡도는 merge sorting과 같은 재귀식으로 나타낼수 있고 결과적으로, O(nlogn)과 동일하다.
코드로 구현하면 다음과 같다.
def maxiSubSum(array):
if len(array) == 1:
return array[0]
# 배열을 반절 나눔 divide
left_max = maxiSubSum(array[:len(array)//2] )
right_max = maxiSubSum(array[len(array)//2:])
# combine
# length//2를 끝 index로 하는 왼쪽 max_sum
lsum = 0
left = []
for i in range((len(array)//2 -1) , -1, -1):
lsum += array[i]
left.append(lsum)
left_sum = max(left)
# length//2를 시작 index로 하는 오른쪽 max_sum
rsum = 0
right = []
for i in range(len(array)//2, len(array)):
rsum += array[i]
right.append(rsum)
right_sum = max(right)
combine_max = left_sum + right_sum
return max(left_max, right_max, combine_max)Kadane 알고리즘
위에서 두가지 알고리즘을 모두 살펴보았지만 사실 이 문제를 풀수있는 제일 효율적인 방법은 Kadane 알고리즘이다.
Kadane 알고리즘의 핵심은 각각의 부분배열의 합은 이전 부분배열의 합에 현재의 인덱스 값을 더한 값이라는 것이다.
이 점을 응용해서 이전 인덱스 가질 수 있는 최대 부분합에 현재의 인덱스 값을 더하여 현재 인덱스가 가질 수 있는 최대 부분합을 구할 수 있다.
예를 들어 배열 A에 A[5]까지의 서브 배열을 구한다고 하자. 아래의 예시에서와 같이 A[5]까지의 서브 배열을 구할 때는 A[[4]의 서브배열에 A[5]를 더한 값이된다는것을 할 수 있다.
그렇다면, A[5]까지의 서브배열 합의 최댓값을 구한다면, A[5]까지의 서브배열의 합은 (A[4]까지의 서브배열의 합) + A[5]의 값이거나 A[4]까지 배열의 합이 음수라면 A[5]자신이 최댓값이 되거나 이 두가지 경우라는 것을 알 수 있다.
- (A[4]까지의 서브배열의 합 중 MAX인 값) + A[5]
- A[5]
이 두가지 상황을 표시한게 빨간 화살표로 표시한 부분이다. 여기서 주목할 부분은 A[5]까지의 서브 배열의 합을 구할 때 A[4]까지의 서브 배열의 값이 사용된다는 것이다.
이런 Kadane 알고리즘을 식으로 표현하면 다음과 같다.
Kadane 알고리즘의 시간복잡도는 O(n)으로 위의 두가지 방법에 비해 확연히 줄어든것을 알 수 있다.
코드로 구현하면 아래와 같다.
def Kadane(array):
# 초기값 설정
local_max = golbal_max = array[0]
for num in array[1:]:
# 부분 수열의 합 구하기
local_max = max(num, local_max + num)
# 전체 배열에서 subarry의 합 최댓갑 구하기
global_max = max(local_max, global_max)
return global_max
이 코드를 바탕으로 우리 문제를 해결하면 다음과 같다. 해당문제는 최대합 뿐만아니라 해당 구간도 출력을 해야한다.
그래서 구간의 시작 인덱스와 끝 인덱스를 저장하고 출력하는 부분을 추가했다.
def Kadane(array):
if (len(array)==1):
return 0, -1, -1
local_max = global_max = array[0]
start_idx = end_idx = tmp_idx = 0
for i in range(1,len(array)):
if array[i] > (local_max+array[i]):
tmp_idx = i #새로운 시작점을 명시해줌
local_max = array[i]
else :
local_max += array[i]
if local_max > global_max:
global_max = local_max
# 구간 갱신
start_idx = tmp_idx
end_idx = i
return global_max, start_idx, end_idx
참조
Kadane’s Algorithm (카데인 알고리즘)
위의 문제는 전체 배열에서의 최대 부분합을 구하는 문제이다. Brute Force 방식으로 문제를 어렵지 않게(?) 해결할 수 있지만, 카데인 알고리즘을 이용하면 O(N)으로 문제를 해결할 수 있다.
medium.com
https://scavienger.tistory.com/19
[Algorithm] Kadane's Algorithm
처음으로 소개할 알고리즘은 Kadane Algorithm 이다. Maximum Subarray Problem 을 푸는 방법중에 하나의 알고리즘이다. 실제로 해당 문제는 Brute-force 로도 풀 수 있고, Divide & Conquer 로도 풀 수 있지만 카데인
scavienger.tistory.com
[알고리즘] 카데인 알고리즘
알고리즘 - 카데인 알고리즘
velog.io
