Maximum Subsequence Sum Problem
20 Sep 2017 | algorithm
이번 글에서는 순서가 있는 숫자들의 최대 부분합을 구하는 문제인 Maximum Subsequence Sum Problem 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의를 정리하였음을 먼저 밝힙니다. 네 가지 접근을 소개할 예정인데요, 계산복잡성이 차례로 줄어듭니다. 그럼 시작하겠습니다.
접근1
다음과 같은 리스트가 있다고 가정해 보겠습니다.
4, -3, 5, -2, -1, 2, 6, -2
이 문제를 가장 단순하게 푸는 방법은 모든 경우의 수를 하나하나 모두 따져보는 것입니다. $i$는 고려 대상 부분 리스트의 왼쪽 끝 인덱스, $j$는 오른쪽 끝 인덱스, Thissum은 고려 대상 부분 리스트의 합, Maxsum은 이 문제의 최종 결론입니다. 다음과 같습니다.
$i$
$j$
Thissum
Maxsum
0
0
4
4
0
1
4+(-3)
4
0
…
…
…
0
7
4+(-3)+5+(-2)+(-1)+2+6+(-2)
11
1
1
-3
11
1
2
(-3)+5
11
…
…
…
…
7
7
-2
11
위 표를 말로 풀어 설명하면 우선 $i$, $j$, Thissum, Maxsum을 모두 0으로 초기화합니다. $i$는 고정시킨 채 $j$를 0부터 리스트 요소 전체 숫자($n$)만큼 훑어가면서 부분 리스트를 만들고 이 리스트의 합을 Thissum으로 정의합니다. 그리고 이를 Maxsum과 비교해 더 큰 값을 Maxsum에 저장합니다. 이를 $i$와 $j$가 모두 $n=7$이 될 때까지 반복합니다. 이 방식의 의사코드는 다음과 같습니다.
Maxsum = 0
for (i=0; i < n; i++)
{
for (j=i; j < n; j++)
{
Thissum = sum(A[i:j])
Maxsum = max(Thissum, Maxsum)
}
}
이 방식의 계산복잡성은 $O(n^3)$이 됩니다. $i$와 관련된 반복문은 $n$번, $j$와 관련된 반복문은 최대 $n$번, Thissum을 구할 때 최대 $n$개의 요소를 계산해야 하기 때문입니다.
접근2
접근1보다 계산복잡성을 낮추는 방법은 Thissum을 구할 때 중복을 좀 피하는 것입니다. 예제 리스트와 그 방식을 나타낸 표는 다음과 같습니다.
4, -3, 5, -2, -1, 2, 6, -2
$i$
$j$
Thissum
Maxsum
0
0
4
4
0
1
4+(-3)
4
0
2
1+5
6
0
3
6+(-2)
6
0
…
…
…
0
7
11+(-2)
11
…
…
…
…
표에서 접근1과의 차이가 느껴지실 지 모르겠습니다. 접근1에서는 Thissum을 구할 때 sum(A[i:j])을 취하여 매번 새로 구하다시피했습니다. 하지만 접근2에서는 직전 계산 결과를 재활용합니다. 예컨대 $i$가 0, $j$가 3일 경우 접근1에서는 4-3+5-2를 계산했다면, 접근2에서는 직전 계산결과인 6에 $j$번째 요소인 -2를 더해 Thissum을 구합니다. 의사코드는 다음과 같습니다.
Maxsum = 0
for (i=0; i < n; i++)
{
for (j=i; j < n; j++)
{
Thissum = sum(A[i:j])
Maxsum = max(Thissum, Maxsum)
}
}
이 방식의 계산복잡성은 $O(n^2)$이 됩니다. $i$와 관련된 반복문은 $n$번, $j$와 관련된 반복문은 최대 $n$번, Thissum을 구할 때는 $O(1)$의 계산만 하면 되기 때문입니다.
접근3
접근3은 분할정복(divide-and-conquer)을 활용한 방식입니다. 분할정복이란 원 문제를 작은 부분문제로 나눠 푼 뒤 그 결과를 합쳐서 문제를 해결하는 알고리즘의 한 종류입니다. 접근3은 분석 대상 리스트를 절반씩 두 부분으로 나눕니다. 다시 예제 리스트를 보겠습니다.
4, -3, 5, -2, -1, 2, 6, -2
위 리스트를 두 부분으로 나누면 [4, -3, 5, -2], [-1, 2, 6, -2]가 됩니다. 왼쪽 리스트의 최대 부분합은 6(4-3+5), 오른쪽 리스트의 최대 부분합은 8(2+6)이 됩니다.
그런데 고려해야 하는 경우의 수가 이것만 있는 것은 아닙니다. 예컨대 [5, -2, -1]처럼 자른 곳(-2와 -1 사이)를 포함하는 부분 리스트도 얼마든지 존재할 수 있기 때문입니다.
중간에 존재하는 케이스의 경우 1)왼쪽 리스트의 마지막 요소(left ending)를 끝으로 하는 부분 리스트의 최대 부분합 2)오른쪽 리스트의 첫 요소(right starting)를 시작으로 하는 부분 리스트의 최대 부분합을 각각 구해 이를 더하면 구할 수 있을 것입니다.
1)에 해당하는 수는 4(-2+5-3+4), 2)는 7(-1+2+6)이므로 중간 케이스의 최대 부분합은 11이 됩니다. 결과적으로는 8, 6, 11 가운데 최대값을 취한 것이 접근3의 결과물이 되겠습니다. 접근3의 의사코드는 다음과 같습니다. left와 right는 각각 고려 대상 리스트의 왼쪽 끝, 오른쪽 끝의 인덱스입니다.
Maxsubsum(A[], left, right)
{
// 종료 조건
if (left == right)
{
maxsum = max(A[left], A[right])
return maxsum
}
// divide&conquer
Center = ⌞(left+right)/2⌟
// [1] 왼쪽
maxleftsum = Maxsubsum(A[], left, center)
// [2] 오른쪽
maxrightsum = Maxsubsum(A[], center+1, right)
// [3] 중간
maxleftbordersum = 0
leftbordersum = 0
// 1) left ending을 끝으로 하는 부분 리스트의 최대 부분합
for (i=center; i>=left; i--)
{
leftbordersum += A[i]
maxleftbordersum = max(maxleftbordersum, leftbordersum)
}
// 2) right starting을 시작으로 하는 부분 리스트의 최대 부분합
for (i=center+1; i<=right; i++)
{
rightbordersum += A[i]
maxrightbordersum = max(maxrightbordersum, rightbordersum)
}
// [1], [2], [3] 가운데 최댓값을 취함
return (max(maxleftsum, maxrightsum, maxleftbordersum+maxrightbordersum))
}
그럼 이 코드가 어떻게 작동하는지 예제 리스트를 기준으로 설명해보겠습니다. 다음 그림과 같습니다.
우선 예제 리스트를 $A$, left는 0, right는 7로 정의해 Maxsubsum 함수에 넣어 실행합니다. 종료조건(0≠7)을 만족시키지 못했으므로 $A$를 반으로 나눠 Maxsubsum 함수를 다시 호출합니다. 두 개 리스트 가운데 왼쪽 [4, -3, 5, -2] 또한 종료조건(0≠3)을 만족시키지 못했으므로 이를 다시 반으로 나눠 Maxsubsum 함수를 다시 호출합니다. 나눠진 왼쪽 리스트인 [4, -3] 또한 종료조건(0≠1)을 만족시키지 못했으므로 이를 다시 반으로 나눠 Maxsubsum 함수를 다시 호출합니다.
[4]가 되어서야 비로소 종료조건(0=0)을 만족하므로 4를 반환합니다. 마찬가지로 [-3]은 -3이 반환될 겁니다.
이번엔 [4, -3]을 볼 차례입니다. 왼쪽 [4]의 최대 부분합은 4, 오른쪽 [-3]은 -3, 중간 최대 부분합은 1입니다. 이 가운데 최댓값 4가 [4,-3]의 결과로 반환됩니다. 동일한 과정을 거쳐 [5, -2]는 5가 반환됩니다.
이번엔 [4, -3, 5, -2]를 볼 차례입니다. 왼쪽 [4, -3]의 최대 부분합은 4, 오른쪽 [5, -2]는 5, 중간 최대 부분합은 6입니다. 이 가운데 최댓값 6이 [4, -3, 5, -2]의 결과로 반환됩니다. 동일한 과정을 거쳐 [-1, 2, 6, -2]는 8이 반환됩니다.
마지막으로 전체 리스트를 고려할 차례입니다. 왼쪽 [4, -3, 5, -2]의 최댓값은 6, 오른쪽 [-1, 2, 6, 2]는 8이며 중간의 최댓값은 11이므로 전체 최댓값을 11이 됩니다.
접근3의 계산복잡성을 따져보겠습니다. 리스트의 요소 수가 $n$이라 할 때 이를 절반씩 나눠 재귀함수를 다시 호출하고, 중간 결과를 계산할 때 $n$개 요소 전체에 대해 따져보게 되므로 다음과 같은 식이 성립합니다. ($c$는 컴퓨터 파워 등에 영향을 받는 상수값)
\[\begin{align*}
T\left( n \right) &=2T\left( \frac { n }{ 2 } \right) +cn\\ &=2\times \left[ 2T\left( \frac { n }{ { 2 }^{ 2 } } \right) +c\frac { n }{ 2 } \right] +cn\\ &={ 2 }^{ 2 }T\left( \frac { n }{ { 2 }^{ 2 } } \right) +2cn\\ &={ 2 }^{ 3 }T\left( \frac { n }{ { 2 }^{ 3 } } \right) +3cn\\ &=...\\ &={ 2 }^{ i }T\left( \frac { n }{ { 2 }^{ i } } \right) +icn
\end{align*}\]
여기에서 $n/2^i$가 1이 될 때까지 반복해야 하므로 로그의 정의에 따라 $i$는 $\log_2n$이 됩니다. 식은 다음과 같이 다시 쓸 수 있습니다.
\[\begin{align*}
T\left( n \right) &={ 2 }^{ \log _{ 2 }{ n } }T\left( 1 \right) +\log _{ 2 }{ n } \times cn\\ &=nT\left( 1 \right) +\log _{ 2 }{ n } \times cn\\ &=O(n)+O(n\log _{ 2 }{ n } )\\ &=O(n\log _{ 2 }{ n } )
\end{align*}\]
접근4
접근4는 부분 합이 음수가 될 경우 그 값은 논리적으로 최대값이 될 수 없다는 점에 착안해 계산량을 확 줄인 방법입니다. 복잡하고 현란한 기법을 쓰는 것보다 문제를 잘 이해하고 정의하는 것이 해결의 첫걸음이라는 교훈을 줍니다. 의사코드는 다음과 같습니다.
summax = 0
sum = 0
for i from 0 to n-1
{
sum = sum + a[i]
if sum < 0 then sum = 0
if summax < sum then summax = sum
}
접근4의 계산복잡도는 $i$에 대해 반복 횟수가 $n$이고, 1회당 연산은 $O(1)$이므로 전체적으로는 $O(n)$이 됩니다.
이번 글에서는 순서가 있는 숫자들의 최대 부분합을 구하는 문제인 Maximum Subsequence Sum Problem 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의를 정리하였음을 먼저 밝힙니다. 네 가지 접근을 소개할 예정인데요, 계산복잡성이 차례로 줄어듭니다. 그럼 시작하겠습니다.
접근1
다음과 같은 리스트가 있다고 가정해 보겠습니다.
4, -3, 5, -2, -1, 2, 6, -2
이 문제를 가장 단순하게 푸는 방법은 모든 경우의 수를 하나하나 모두 따져보는 것입니다. $i$는 고려 대상 부분 리스트의 왼쪽 끝 인덱스, $j$는 오른쪽 끝 인덱스, Thissum은 고려 대상 부분 리스트의 합, Maxsum은 이 문제의 최종 결론입니다. 다음과 같습니다.
| $i$ | $j$ | Thissum | Maxsum |
|---|---|---|---|
| 0 | 0 | 4 | 4 |
| 0 | 1 | 4+(-3) | 4 |
| 0 | … | … | … |
| 0 | 7 | 4+(-3)+5+(-2)+(-1)+2+6+(-2) | 11 |
| 1 | 1 | -3 | 11 |
| 1 | 2 | (-3)+5 | 11 |
| … | … | … | … |
| 7 | 7 | -2 | 11 |
위 표를 말로 풀어 설명하면 우선 $i$, $j$, Thissum, Maxsum을 모두 0으로 초기화합니다. $i$는 고정시킨 채 $j$를 0부터 리스트 요소 전체 숫자($n$)만큼 훑어가면서 부분 리스트를 만들고 이 리스트의 합을 Thissum으로 정의합니다. 그리고 이를 Maxsum과 비교해 더 큰 값을 Maxsum에 저장합니다. 이를 $i$와 $j$가 모두 $n=7$이 될 때까지 반복합니다. 이 방식의 의사코드는 다음과 같습니다.
Maxsum = 0
for (i=0; i < n; i++)
{
for (j=i; j < n; j++)
{
Thissum = sum(A[i:j])
Maxsum = max(Thissum, Maxsum)
}
}
이 방식의 계산복잡성은 $O(n^3)$이 됩니다. $i$와 관련된 반복문은 $n$번, $j$와 관련된 반복문은 최대 $n$번, Thissum을 구할 때 최대 $n$개의 요소를 계산해야 하기 때문입니다.
접근2
접근1보다 계산복잡성을 낮추는 방법은 Thissum을 구할 때 중복을 좀 피하는 것입니다. 예제 리스트와 그 방식을 나타낸 표는 다음과 같습니다.
4, -3, 5, -2, -1, 2, 6, -2
| $i$ | $j$ | Thissum | Maxsum |
|---|---|---|---|
| 0 | 0 | 4 | 4 |
| 0 | 1 | 4+(-3) | 4 |
| 0 | 2 | 1+5 | 6 |
| 0 | 3 | 6+(-2) | 6 |
| 0 | … | … | … |
| 0 | 7 | 11+(-2) | 11 |
| … | … | … | … |
표에서 접근1과의 차이가 느껴지실 지 모르겠습니다. 접근1에서는 Thissum을 구할 때 sum(A[i:j])을 취하여 매번 새로 구하다시피했습니다. 하지만 접근2에서는 직전 계산 결과를 재활용합니다. 예컨대 $i$가 0, $j$가 3일 경우 접근1에서는 4-3+5-2를 계산했다면, 접근2에서는 직전 계산결과인 6에 $j$번째 요소인 -2를 더해 Thissum을 구합니다. 의사코드는 다음과 같습니다.
Maxsum = 0
for (i=0; i < n; i++)
{
for (j=i; j < n; j++)
{
Thissum = sum(A[i:j])
Maxsum = max(Thissum, Maxsum)
}
}
이 방식의 계산복잡성은 $O(n^2)$이 됩니다. $i$와 관련된 반복문은 $n$번, $j$와 관련된 반복문은 최대 $n$번, Thissum을 구할 때는 $O(1)$의 계산만 하면 되기 때문입니다.
접근3
접근3은 분할정복(divide-and-conquer)을 활용한 방식입니다. 분할정복이란 원 문제를 작은 부분문제로 나눠 푼 뒤 그 결과를 합쳐서 문제를 해결하는 알고리즘의 한 종류입니다. 접근3은 분석 대상 리스트를 절반씩 두 부분으로 나눕니다. 다시 예제 리스트를 보겠습니다.
4, -3, 5, -2, -1, 2, 6, -2
위 리스트를 두 부분으로 나누면 [4, -3, 5, -2], [-1, 2, 6, -2]가 됩니다. 왼쪽 리스트의 최대 부분합은 6(4-3+5), 오른쪽 리스트의 최대 부분합은 8(2+6)이 됩니다.
그런데 고려해야 하는 경우의 수가 이것만 있는 것은 아닙니다. 예컨대 [5, -2, -1]처럼 자른 곳(-2와 -1 사이)를 포함하는 부분 리스트도 얼마든지 존재할 수 있기 때문입니다.
중간에 존재하는 케이스의 경우 1)왼쪽 리스트의 마지막 요소(left ending)를 끝으로 하는 부분 리스트의 최대 부분합 2)오른쪽 리스트의 첫 요소(right starting)를 시작으로 하는 부분 리스트의 최대 부분합을 각각 구해 이를 더하면 구할 수 있을 것입니다.
1)에 해당하는 수는 4(-2+5-3+4), 2)는 7(-1+2+6)이므로 중간 케이스의 최대 부분합은 11이 됩니다. 결과적으로는 8, 6, 11 가운데 최대값을 취한 것이 접근3의 결과물이 되겠습니다. 접근3의 의사코드는 다음과 같습니다. left와 right는 각각 고려 대상 리스트의 왼쪽 끝, 오른쪽 끝의 인덱스입니다.
Maxsubsum(A[], left, right)
{
// 종료 조건
if (left == right)
{
maxsum = max(A[left], A[right])
return maxsum
}
// divide&conquer
Center = ⌞(left+right)/2⌟
// [1] 왼쪽
maxleftsum = Maxsubsum(A[], left, center)
// [2] 오른쪽
maxrightsum = Maxsubsum(A[], center+1, right)
// [3] 중간
maxleftbordersum = 0
leftbordersum = 0
// 1) left ending을 끝으로 하는 부분 리스트의 최대 부분합
for (i=center; i>=left; i--)
{
leftbordersum += A[i]
maxleftbordersum = max(maxleftbordersum, leftbordersum)
}
// 2) right starting을 시작으로 하는 부분 리스트의 최대 부분합
for (i=center+1; i<=right; i++)
{
rightbordersum += A[i]
maxrightbordersum = max(maxrightbordersum, rightbordersum)
}
// [1], [2], [3] 가운데 최댓값을 취함
return (max(maxleftsum, maxrightsum, maxleftbordersum+maxrightbordersum))
}
그럼 이 코드가 어떻게 작동하는지 예제 리스트를 기준으로 설명해보겠습니다. 다음 그림과 같습니다.
우선 예제 리스트를 $A$, left는 0, right는 7로 정의해 Maxsubsum 함수에 넣어 실행합니다. 종료조건(0≠7)을 만족시키지 못했으므로 $A$를 반으로 나눠 Maxsubsum 함수를 다시 호출합니다. 두 개 리스트 가운데 왼쪽 [4, -3, 5, -2] 또한 종료조건(0≠3)을 만족시키지 못했으므로 이를 다시 반으로 나눠 Maxsubsum 함수를 다시 호출합니다. 나눠진 왼쪽 리스트인 [4, -3] 또한 종료조건(0≠1)을 만족시키지 못했으므로 이를 다시 반으로 나눠 Maxsubsum 함수를 다시 호출합니다.
[4]가 되어서야 비로소 종료조건(0=0)을 만족하므로 4를 반환합니다. 마찬가지로 [-3]은 -3이 반환될 겁니다.
이번엔 [4, -3]을 볼 차례입니다. 왼쪽 [4]의 최대 부분합은 4, 오른쪽 [-3]은 -3, 중간 최대 부분합은 1입니다. 이 가운데 최댓값 4가 [4,-3]의 결과로 반환됩니다. 동일한 과정을 거쳐 [5, -2]는 5가 반환됩니다.
이번엔 [4, -3, 5, -2]를 볼 차례입니다. 왼쪽 [4, -3]의 최대 부분합은 4, 오른쪽 [5, -2]는 5, 중간 최대 부분합은 6입니다. 이 가운데 최댓값 6이 [4, -3, 5, -2]의 결과로 반환됩니다. 동일한 과정을 거쳐 [-1, 2, 6, -2]는 8이 반환됩니다.
마지막으로 전체 리스트를 고려할 차례입니다. 왼쪽 [4, -3, 5, -2]의 최댓값은 6, 오른쪽 [-1, 2, 6, 2]는 8이며 중간의 최댓값은 11이므로 전체 최댓값을 11이 됩니다.
접근3의 계산복잡성을 따져보겠습니다. 리스트의 요소 수가 $n$이라 할 때 이를 절반씩 나눠 재귀함수를 다시 호출하고, 중간 결과를 계산할 때 $n$개 요소 전체에 대해 따져보게 되므로 다음과 같은 식이 성립합니다. ($c$는 컴퓨터 파워 등에 영향을 받는 상수값)
\[\begin{align*} T\left( n \right) &=2T\left( \frac { n }{ 2 } \right) +cn\\ &=2\times \left[ 2T\left( \frac { n }{ { 2 }^{ 2 } } \right) +c\frac { n }{ 2 } \right] +cn\\ &={ 2 }^{ 2 }T\left( \frac { n }{ { 2 }^{ 2 } } \right) +2cn\\ &={ 2 }^{ 3 }T\left( \frac { n }{ { 2 }^{ 3 } } \right) +3cn\\ &=...\\ &={ 2 }^{ i }T\left( \frac { n }{ { 2 }^{ i } } \right) +icn \end{align*}\]여기에서 $n/2^i$가 1이 될 때까지 반복해야 하므로 로그의 정의에 따라 $i$는 $\log_2n$이 됩니다. 식은 다음과 같이 다시 쓸 수 있습니다.
\[\begin{align*} T\left( n \right) &={ 2 }^{ \log _{ 2 }{ n } }T\left( 1 \right) +\log _{ 2 }{ n } \times cn\\ &=nT\left( 1 \right) +\log _{ 2 }{ n } \times cn\\ &=O(n)+O(n\log _{ 2 }{ n } )\\ &=O(n\log _{ 2 }{ n } ) \end{align*}\]접근4
접근4는 부분 합이 음수가 될 경우 그 값은 논리적으로 최대값이 될 수 없다는 점에 착안해 계산량을 확 줄인 방법입니다. 복잡하고 현란한 기법을 쓰는 것보다 문제를 잘 이해하고 정의하는 것이 해결의 첫걸음이라는 교훈을 줍니다. 의사코드는 다음과 같습니다.
summax = 0
sum = 0
for i from 0 to n-1
{
sum = sum + a[i]
if sum < 0 then sum = 0
if summax < sum then summax = sum
}
접근4의 계산복잡도는 $i$에 대해 반복 횟수가 $n$이고, 1회당 연산은 $O(1)$이므로 전체적으로는 $O(n)$이 됩니다.
Comments