[C언어] 최대 연속부분수열의 합

[C언어] 최대 연속부분수열의 합

본 포스팅은 도서 "문제로 풀어보는 알고리즘"(황인욱, 김용혁 지음)을 공부한 내용을 정리하기 위한 글임을 밝힙니다.

연속부분수열

어떤 수열의 연속부분수열이란 그 수열의 원소를 하나 이상 연속하여 선택한 부분수열을 말한다. 예를 들어 아래와 같은 수열(배열)이 있다고 하자.

33

31

92

-38

11

12

4

-17

-1

21

다음은 이 수열의 연속부분수열들이다.

33

31

92

-38

11

12

4

-17

-1

21

33

31

92

-38

11

12

4

-17

-1

21

33

31

92

-38

11

12

4

-17

-1

21

  첫 번째 연속부분수열의 합은 -38 + 11 + 12 + 4 = -11이고, 두 번째는 -1 + 21 = 20, 세 번째는 33 + 31 + 92 + (-38) + 11 + 12 = 141이다. 연속부분수열의 합 중 가장 큰 것은 33 + 31 + 92 = 156이다.

C언어 구현 (1) - O(n^3)

가장 먼저 떠올릴 수 있는 방법은 아래와 같을 것이다.

int max_consecutive_sum(int s[], int n) {
int i, j, k, sum, max_sum = s[0];

for(i = 0; i < n; i++) {
for(j = i; j < n; j++) {
sum = 0;
for(k = i; k <= j; k++)
sum += s[k];
if(sum > max_sum)
max_sum = sum;
}
}
return max_sum;
}

위 코드에서 i와 j는 각각 연속부분수열의 시작과 끝을 나타낸다. 따라서 위 함수는 주어진 배열에서 가능한 시작과 끝 위치 모두에 대해 합을 구해본다.

위 코드는 삼중 루프를 사용한 코드로, 시간 복잡도가 O(n^3)이다. 즉, 엄청 느리다..

C언어 구현 (2) - O(n^2)

int max_consecutive_sum2(int s[], int n) {
int i, j, sum, max_sum = s[0];

for(i = 0; i < n; i++) {
sum = 0;
for(j = i; j < n; j++) {
sum += s[j];
if(sum > max_sum)
max_sum = sum;
}
}
return max_sum;
}

위 코드는 이중 루프에서 n^2에 비례하는 시간을 사용한다. 가능한 모든 i와 j 쌍에 대해 부분수열의 합을 구하지만, 앞에서 구한 합을 이용하기 때문에 앞선 max_consecutive_sum() 함수보다 훨씬 빠르다.

이 정도만 되도 사실 어느정도 성능은 보장된 알고리즘이라 볼 수 있지만, 왠지 만족스럽지 않다..

더 빠른 알고리즘은 없을까?

C언어 구현 (3) - O(n)

int c[N];
void calculate_max_consecutive_sum(int s[], int n) {
int i;

c[0] = s[0];
for(i = 1; i < n; i++)
c[i] = (s[i] > s[i] + c[i-1]) ? s[i] : s[i] + c[i-1];
}

int find_max_consecutive_sum(int s[], int n) {
int max_sum = 0, i;

for(i = 0; i < n; i++) {
if(c[i] > max_sum)
max_sum = c[i];
}
return max_sum;
}

동적 계획법(Dynamic Programming)을 이용한 방법이다. 위 코드로 작성 시 시간 복잡도는 O(n)으로, 앞선 두가지 방식에 비해 엄청나게 빠른 속도를 자랑한다. 책에 나와있는 바로는 100만개의 데이터 배열을 처리하는데 0.5초도 걸리지 않는 방식이라고 한다.

데이터의 사이즈가 커지면 커질수록 재귀함수의 오버헤드가 기하급수적으로 증가하기 때문에 사실상 시간적으로나 공간적으로 효율적인 구현을 하기 어렵기 때문에, 항상 점화식을 세운 후 중복 계산이 없는지 체크하여서 동적 계획법이나 메모이제이션 기법을 통하여 보다 빠른 알고리즘으로 구현하도록 하는 연습을 꾸준히 해야겠다.

위와 같은 알고리즘으로 풀 수 있는 문제로는 백준 1912번(연속합 문제)가 있겠다.

백준 1912번(연속합)