(연속된/연속되지 않은) 최대 부분합 구하기 {O(n^3), O(n^2), O(n)}
대회에도 나갔을때도, 백준이나 codeup 에서 풀문제를 찾아볼 때도 항상 내 눈에 보였지만 푸는 방법이 전혀 감이 잡히지 않아 그냥 넘어갔던 문제들이 있다.
바로 "연속된 최대 부분합"을 구하는 문제였다.
"연속된 최대 부분합"이란 숫자들로 이뤄진 1차원 배열에서 이어져 있는 특정 부분의 합이 최대가 되는 부분을 말한다.
즉, -9 4 -2 8 -2 4 9 -8 이라는 배열이 있다면 이때 "연속된 최대 부분합"은 4 -2 8 -2 4 9 가 된다.
1. 연속으로 이어져 있고
2. 합이 최대가 되기 때문이다.
그래서 이때의 합을 구하라고 한다면 4-2+8-2+4+9 = 21 이된다.
입력값이 4, -2, 8, -2, 4, 9 라면 21을 출력하면 되는 것이다.
이런 문제들은 정말 많이 볼수 있고 이를 응용함에 따라 난이도가 천차만별로 달라지기도 한다.
그래서 이 글에서는 가장 기본적인 "연속된 최대 부분합"을 구하는 방법과 "하나를 제외한 연속된 최대 부분합"을 구하는 방법을 설명하려 한다.
이 문제들은 백준 1912, 13398 로도 나와있는 최대 부분합의 대표적인 두 예제이다.
연속된 최대 부분합 구하기 (1912)
하나를 제외한 연속된 최대 부분합 구하기 (13398)
연속된 최대 부분합 구하기
연속된 최대부분합을 구할 수 있는 방법은 다양하다.
그 이유는 범위에 따라서 쓸 수 있는 알고리즘의 범위가 제한되기 때문이다.
- https://codeup.kr/problem.php?id=3700
- https://codeup.kr/problem.php?id=3705
- https://www.acmicpc.net/problem/1912
이 1번 Codeup 문제의 경우에는 입력값의 범위가 100까지 밖에 되지 않기에 for문을 3~4중첩까지도 할 수 있다.
그렇기에 이 문제의 경우에는 Brute Force를 이용해 모든 부분 배열의 합을 비교해줄 수 있다.
#include <stdio.h>
#include <stdlib.h>
int a[101]; // 입력값 저장
int n; // 입력개수
int max_of_sum() //연속된 최대 부분합 반환하는 함수
{
int max = -9999999;
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
int s = 0; // i~j 까지의 부분합을 저장할 변수 s
for(int k = i; k <= j; k++)
s += a[k];
if(s > max) max = s; // i~j 까지의 부분합이 기존의 최대합 보다 크다면 변경
}
}
return max;
}
int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
printf("%d", max_of_sum());
}i와 j를 처음부터 n번째까지 늘려가며 그 사이의 합을 max와 비교하며 늘려가는 것이다.
무려 시간복잡도가 O(n^3)이기에 복잡하고 어렵다. (물론 이 문제에서는 시간초과 없이 해결된다.)
이 코드에서는 k를 다시 i~j까지 돌리는데 이를 O(n^2)으로 줄일 수 있다.
이렇게 말이다.
#include <stdio.h>
#include <stdlib.h>
int a[101]; // 입력값 저장
int n; // 입력개수
int max_of_sum() //연속된 최대 부분합 반환하는 함수
{
int max = -9999999;
for(int i = 0; i < n; i++) {
int s=0; // i~j 까지의 부분합을 저장할 변수 s
for(int j = i; j < n; j++) {
s += a[j];
if(s > max) max = s; // i~j 까지의 부분합이 기존의 최대합 보다 크다면 변경
}
}
return max;
}
int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
printf("%d", max_of_sum());
}어차피 k가 i~j 를 다시한번 돌기에 이를 처음부터 j가 i~n 을 돌때 그때마다 최대합을 비교해주는 방법으로 말이다.
여기까진 아마 누구나 쉽게 할 수 있을 것이고 나또한 여기까지는 쉽게 할 수 있었다.
하지만 이렇게 해도 O(n^2)이기에 n이 10000 이상이 되면 2,3 번 문제를 푸는데 시간이 1초를 넘어가게 되어 시간초과가 날 수 있다.
그래서 O(n) 혹은 O(nlogn) 정도의 알고리즘이 필요했다.
이때 Kadane's Algorithm을 찾게 됐다.
Kadane 알고리즘은 점화식을 이용해 "연속된 부분합" 사이의 관계를 수식으로 이끌어내어 O(n)으로 해결할 수 있는 알고리즘 이었다.
점화식. 누가봐도 DP의 느낌이 강하게 온다.
Kadane's Algorithm
Kadane 알고리즘에서는 부분합 사이의 관계를 이끌어 내기 위해 그냥 부분합이 아닌, i번째 값으로 끝나는 부분 배열로 나눠서 생각했다.
예를들어 0~ (n-1) 까지의 배열이 있다면
m[i] = i번째 원소로 끝나는 배열의 합 중 최대값
을 의미하게 된다.
i번째 원소의 값이 ai 라고 한다면
m[0] = a0
m[1] = max( a1, a0+a1)
m[2] = max(a2, a2 +a1, a2+a1+a0)
m[3] = max(a3, a3+a2, a3+a2+a1, a3+a2+a1+a0)
가 되는 것이다.
이렇게 됐을 때 한가지 규칙성을 발견할 수 있다.
예를 들어 m[3] = max(a3, a3+a2, a3+a2+a1, a3+a2+a1+a0) 이지만 여기서 a3를 제외하고 생각한다면
max(a3+a2, a3+a2+a1, a3+a2+a1+a0) 가 되는데 이는 m[2] + a3 로 나타낼 수 있게 된다.
그렇다면 m[3]는 m[2]+a3 와 a3중 최댓값을 나타낸 것이기에
m[3] = max(m[2]+a3, a3) 가 된다는 점을 알 수 있다.
이를 일반화 한다면
m[0] = a0
m[i] = max(m[i-1]+ai, ai)
라는 점화식으로 나타낼 수 있다.
... 다시 문제로 돌아와서
이때부턴 DP로 간단히 구현할 수 있었다.
위에 글로 정리할 점화식 방법과 아래 코드를 비교하면서 보면 이해가 쉬울 것이다.
#include <stdio.h>
int max_of(int a,int b) //최댓값을 반환하는 함수 max(a,b)의 역할
{
return (a>b) ? a:b; //삼항연산자
}
int main(){
int n, m; // 입력개수 n, n개의 입력값 m -> ai의 역할
scanf("%d", &n);
int max= -999999, memo= 0;
// max : 최댓값; memo : m[i-1]의 역할, i-1번째 원소를 포함한 부분합의 최댓값을 나타냄
for (int i=0; i<n; i++) {
scanf("%d", &m);
memo= max_of(m, memo+m); // m[i]= max(m[i-1]+ai, ai) 를 나타낸 코드
max= max_of(memo, max); // 기존의 최댓값과 비교
}
printf("%d",max);
}원래의 나였다면 memo[] 로 해서 정석적인 점화식에 쓰이는 메모이제이션 기법처럼 이전의 값을 저장하면서 하였을 텐데
최근에 수업시간에 계단오르기 문제의 풀이에서 이전값들을 굳이 저장하지 않고 m[i]를 구하는데 그 바로전의 값만 필요하다면 그냥 변수에 저장해서 같이 상향하는 방법으로도 풀 수있다는 걸 알게 되었기에 배열을 전혀 사용하지 않고
memo를 (i-1) 에서의 값으로 계속 상향시켜 주며 해결 할 수 있었다.
연속되지 않은 최대 부분합 구하기
이제 연속되지 않은 최대 부분합 구하기 문제이다.
https://www.acmicpc.net/problem/13398
바로 연속된 부분에서 하나의 원소를 제거하고 합을 구할 수 있는 것이다. (물론, 반드시 제외해야 하는건 아니다)
예를 들면
| 2 | 4 | 6 | -20 | 3 | 6 | 9 |
가 있으면 "연속된 배열의 최대 부분합"에선 3+6+9 = 18이 최대였을 것이다.
하지만 연속되지 않은 경우에서는 [-20] 이라는 값을 제외하고 합을 구할 수 있다.
즉, 이때는 "연속되지 않은 배열의 최대 부분합"이 2+4+6+3+6+9 = 30 이 되는 것이다.
30>18 이므로 출력되는 값은 30이 된다.
막상 이 문제를 접하면 매우 막막해 보일 수 있지만 위에서 설명한대로 코드도 그대로 작성하면 된다.
"연속된 배열의 최대 부분합" 을 Kadane's algorithm 으로 구하고
"연속되지 않은 배열의 최대 부분합"을 또 구해서 이중 큰 값을 출력하면 되기 때문이다.
여기서 중요한점은 "연속되지 않은 배열의 최대 부분합"을 어떻게 구하냐는 것이다.
잘 생각해보니 제외하는 원소가 i번째 라고 한다면 i-1을 포함하는 최대합 + (i+1)을 포함하는 최대합을 구하면 되는 것이었고 이때 (i+1)을 포함하는 i+1이 부분배열의 마지막 원소가 아닌 첫번째 원소이기에
kadane's algorithm 을 역순으로 뒤에서 실행한 m[i+1]이 그 값이 되기에 의외로 간단히 해결할 수 있었다.
쉽게 말하자면
m[i] = i번째 원소로 끝나는 배열의 합 중 최대값 reverse_m[i] = i번째 원소로 시작하는 배열의 합 중 최대값
이라고 할때
for(int i=0; i<n-2; i++) // [i-1] , [i+1] 이 있으므로 0하고 n-1은 제외한다해당 범위내에서 i번째 원소를 제외한 최댓값을 구할 때 m[i-1] + reverse_m[i+1] 을 구하면 되는 것이다.
전체 코드는 다음과 같다 (코드에서는 m[i], reverse_m[i+1] 대신 left, right 를 사용하였다)
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100001
int a[SIZE]; // 입력값 저장
int left[SIZE];
//[i]번째 값이 마지막이 되는 배열의 최대 부분합값을 저장하는 배열 m[]
int right[SIZE];
//[i]번째 값이 처음이 되는 배열의 최대 부분합값을 저장하는 배열 reverse_m[]
int n; // 입력개수
int max = -9999999;
int max_of(int a,int b) //최댓값을 반환하는 함수 max(a,b)의 역할
{
return (a>b) ? a:b; //삼항연산자
}
int max_of_sum() //연속된 최대 부분합 반환하는 함수
{
int sum=0; // 최대 부분합을 저장하는 변수
sum= left[0]= a[0]; // 기본값을 처음 입력값으로 초기화
for(int i=0; i<n; i++)
{
left[i]= max_of(left[i-1] + a[i], a[i]);
sum= max_of(sum, left[i]);
}
// 연속된 최대 부분합을 구하는 문제를 푸는 것과 동일하게 풀고, 그 값들을 left[] 에 저장한다.
right[n] = a[n];
for (int i=n-1; i>=0; i--)
{
right[i]= max_of(a[i], right[i+1] + a[i]);
}
// 동일하게 right[]에 들어갈 값들을 다 구하고, 저장한다. (방법은 동일하고 순서만 달라진다)
for (int i=0;i<=n-2;i++)
{
sum= max_of(sum,left[i-1]+ right[i+1]);
}
// 연속된 경우의 최대합(sum)과 연속되지 않은 경우의 합을 하나하나 비교해준다.
// 가장 큰값을 최종적으로 sum에 저장한다
return sum; // sum 값 리턴
}
int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
printf("%d", max_of_sum());
}이렇게 코드가 완성된다.
물론 여기서 중간에 i의 범위가 0~ (n-1)까지 일때 [i-1]의 값을 불러오기에 이상한 값이 들어와서 값이 달라질 수도 있기에
n 이 1인 경우를 따로 분리해서 처리해주고, i의 범위를 1부터 시작하는 것이 좀 더 안정적이라고 할 수 있다.
이렇게 연속된 최대 부분합과 연속되지 않은 최대 부분합을 구할 수있는 방법과 알고리즘에 대해 알아보았다!
그럼 이만!