[알고리즘] 연속 부분 수열의 합

 

연속 부분 수열의 합?

: 비어 있지 않는 숫자 배열에서 합이 최대가 되는 연속된 부분수열 구간의 합

 

아래와 같은 정수 배열이 있을 때,

-2

-3

4

-1

-2

1

5

-3

4부터 5까지의 연속된 구간의 합은 7로 다른 부분 배열의 합보다 항상 크다.

이처럼 연속적인 부분 수열의 최대 합을 구하는 것이 이 문제의 목표이다.

 

 

 

---

 

1) 완전 탐색(Brute Force) : 가능한 모든 경우의 수를 조사해 찾는 알고리즘

 

👉 배열의 인덱스를 0부터 시작해 한 단계씩 나아가면서 중간값을 사용해 결과를 낸다.

 

 

먼저, 고려해야 할 부분은

1. 크기가 1인 부분 수열의 합
2. 현재까지 구한 답에 현재 배열의 인덱스 값을 더해서 끝내는 경우
3. 현재까지 구한 값을 버리고 현재 인덱스 값으로 다시 시작하는 경우
4. 현재 값과 현재까지 만든 값을 포함해 계속 하는 경우

 

 

min = -2 ** 31 -1 # 하한선 설정

def BruteForce(arr):
	n = len(arr)
    
    def find(idx, ans):
    	if idx == n: # 배열의 마지막에 도달한 경우
        	return min
        # 위에서 정한 4가지 경우의 수 중 최대값
        ans = max(arr[idx], ans + arr[idx], find(idx+1, arr[idx], find(idx+1, ans+arr[idx]))
        return ans
    return find(0,0)

 

- idx : 현재 인덱스 값

- ans : 현재까지 구한 중간합

 

👉 시간복잡도 : O(2^n)

   - 배열의 크기가 커질수록, 총 실행횟수가 2배씩 증가한다.

 

---

 

2) 부분합(Partial Sum) 수열 : 배열의 시작부터 현재 위치까지의 원소들의 합을 구한 배열

 

👉 인덱스 i의 값에 원 수열 arr의 0부터 i까지의 합을 구한 수열 이용

 

pSum : arr의 부분합 수열
                 i
pSum[i] = ∑ arr_i
               i =0

부분합 수열은 배열의 특정 구간의 합을 구하는데 유용하다.

 

 

어떤 수열의 [low, high] 구간의 합을 구하려고 할 때,

   i
  ∑     arr_i = pSum[high] - pSum[low-1]
i = low

위 식을 통해서 구할 수 있다.

 

 

이 식을 이용해 수열의 모든 부분 구간에 대한 구간을 구한 후 최대값을 도출할 수 있다.

 

def PartialSum(arr):
	arr = [0] + arr # 배열 앞에 '0' 추가
    				# 구간 [0, 3] 에서 low - 1하면 인덱스가 -1이기 때문에 
    	n = len(arr)
    	pSum = [0] * n
    	ans = min
    
    	for i in range(1, n):
    		pSum[i] = pSum[i-1] + arr[i]
        
    	for high in range(1, n):
    		for low in range(1, high + 1): # 부분수열의 크기가 1일 때도 계산됨
        		ans = max(ans, pSum[high] - pSum[low-1])
    	return ans

 

👉 시간복잡도 : O(n^2)

    - for 문의 중첩

 

 

---

 

3) 분할정복 : 하나의 문제를 여러 문제로 분할해 문제를 해결하는 알고리즘

 

👉 배열을 절반으로 나눠 오른쪽 배열과 왼쪽 배열로 나눈다. 이때, 최대 합 부분인 두 배열 중에 속해 있을 수도 있고, 두 배열 사이에 걸쳐 있을 수도 있다.

 

-2

-3

4

-1

-2

1

5

-3

 

👇

왼쪽 배열

 

-2

-3

4

-1

 

오른쪽 배열

 

-2

1

5

-3

 

 

따라서 고려해야 할 부분은,

1. 왼쪽 배열에 있는 경우
2. 오른쪽 배열에 있는 경우
3. 두 배열에 걸쳐 있는 경우

 

def DivideAndConquer(arr):
    n = len(arr)
    
    def find(low, high):
    	if low == high: # 원소의 개수가 1개인 경우
        	return arr[low]
            
        mid = (low + high) // 2
        left = find(low, mid) # 왼쪽 배열에서의 최대합
        right = find(mid + 1, high) # 오른쪽 배열에서의 최대합
        
        tmp = 0
        left_part = min
        for i in range(mid, low - 1, -1):
        	tmp += arr[i]
            left_part = max(left_part, tmp)
            
        tmp = 0
        right_part = min
        for i in range(mid+1, high+1):
        	tmp += arr[i]
            right_part = max(right_part, tmp)
            
        return max(left, right, left_part + right_part)
        
    return find(0, n-1)

 

👉 시간복잡도 : O(nlogn)

    - 배열의 처음부터 끝가지 스캔 : O(n)

    - 배열을 절반으로 나눔 : O(logn)

 

 

---

4) 동적계획법(Dynamic Programming) : 특정 범위까지의 값을 구하기 위해 다른 범위의 값을 이용해 효율적으로 구하는 알고리즘

 

👉 인덱스 0 ~ 끝까지 캐시를 채운 후 캐시의 최대값 반환

 

 

def DynamicProgramming(arr):
	cache = [None] * len(arr)
    	cache[0] = arr[0]
    
    	for i in range(1, len(arr)):
    		cache[i] = max(0, cache[i-1]) + arr[i]
        
	return max(cache)

 

- 순환식 : f(i) = max(0, f(i-1)) + cache[i]

👉 시간복잡도 : O(n)

 

 

---

참고

https://shoark7.github.io/programming/algorithm/4-ways-to-get-subarray-consecutive-sum

https://jungmonster.tistory.com/126