Graphics Programming

Maximum Sum (최대부분합) 본문

Season 1/Problem solving

Maximum Sum (최대부분합)

minseoklee 2013. 12. 24. 09:51

위키피디아(http://en.wikipedia.org/wiki/Maximum_subarray_problem)를 보니 정식 이름은 Maximum subarray problem인 것 같다.

문제 소개는 출처에 있다. 가장 먼저 모든 경우를 검사하는 Θ(nn) 알고리즘이 떠올랐다. 원소가 n개일 때 부분합의 총 개수는 양 끝을 선택하는 방법의 개수로서 C(n,2) = n(n+1)/2 개다. 모든 부분합을 구하여 그 중 최댓값을 선택한다.

예를 들어 입력이 [1, -2, 5, -3, 6, 2] 이라면 i ~ j번째 원소의 합을 다음과 같이 표로 나타낼 수 있다.

 (i, j)

0

1

2

3

4

5

0

-1 

4

 7

9

1


-2

3

0

6

8

2



5

2

8

10

3




-3

3

5

4





6

8

5






2


위의 예에서 답은 5, -3, 6, 2를 더한 10이다. 위 코드를 C로 간단하게 작성하고 실행했다.


// Θ(nn) 알고리즘.

#include <stdio.h>
#include <stdlib.h>

void main() {
  int* ary;
  int i, j, num, max=-65536, sum;

  scanf("%d", &num);
  ary = (int*)malloc(sizeof(int) * num);
  for(i=0; i<num; i++) scanf("%d", ary+i);

  for(i=0; i<num; i++){
    sum = 0;
    for(j=i; j<num; j++){
      sum += ary[j];
      if(sum > max) max = sum;
    }
  }

  printf("%d", max);
  free(ary);
}

하지만 Θ(nn) 알고리즘이라 너무 느렸는지 9번 테스트에서 시간 제한 초과로 실패해버렸다. 더 빠른 알고리즘이 필요했고, 일단 표에서 계산을 생략할 수 있는 중복 부분을 찾아봤지만 딱히 찾을 수 없었다. 발상을 전환해서 이번에는 음수에 주목했다. 문제는 최댓값을 구하는 최대화 문제이고, 음수를 더하면 무조건 합이 작아지는 것에서 출발했다.

입력을 받으면 서로 인접한 양수/음수들을 모두 더해서 한 수로 만들어보자. 그러면 입력은 [양수 음수 양수 ... 음수 양수] 꼴이 되어 무조건 양수와 음수가 번갈아 나온다.

[1, -2, 5, -3, 6, 2] -> [1, -2, 5, -3, 8]

이제 1부터 차례대로 더해보자. -2는 음수여서 더해도 도움이 안 된다. 그러니 항상 음수와 그 다음 양수를 함께 고려한다. -2와 5를 더하면 3으로 전체 합을 늘린다. 이제 합이 4다. -3과 8을 더하면 5로 전체 합을 늘린다. 따라서 1에서 8까지 다 더해보면 합이 9다. 하지만 이 값은 최댓값이 아니다. 무엇을 놓쳤을까?

1과 -2를 더하면 -1이다. 따라서 5부터 시작해서 5, -3, 8을 더하는 게 합이 더 크다. 다음과 같은 절차를 추가하면 최댓값을 올바르게 구할 수 있다.

0 ~ 2번 원소인 1, -2, 5를 더하면 4다. 이 값은 2번째 원소인 5보다 작으므로 5에서 구간을 새로 시작한다. 5, -3, 8을 더하면 10으로 8보다 크므로 구간의 시작으로 5를 그대로 쓴다.

다른 예를 들어서 입력이 [1, 2, -4, -1, 5, 7, -10, 3, 6] 일 경우 [3, -5, 12, -10, 9] 로 줄일 수 있다. 3에서 구간을 시작해서 3, -5, 12를 더하면 10으로 12보다 작으므로 12에서 구간을 새로 시작한다. 12, -10, 9를 더하면 11로 12보다 작으므로 9 다음에서 구간을 새로 시작한다. 단 이 예에서는 9가 끝이므로 12가 최댓값이고 루프가 끝난다. 이렇게 여러 구간의 합을 구하고 그 중 최댓값을 출력한다.

이 방법에는 예외가 한 가지 있는데 모든 원소가 양수가 아닐 경우이다. 이 때는 다 더해서 한 수로 만들어버리면 안 되고 0이 있으면 0을, 없으면 0에 가장 가까운 음수를 답으로 출력한다.

그림을 넣어서 깔끔하게 설명하고 싶지만 빌어먹을 사지방이라 파일 업로드가 막힌다. 내가 군인이라니

C로 작성해서 실행한 결과 논리 오류, 시간 초과 없이 테스트를 무사히 통과했다.

// Θ(n) 알고리즘.
#include <stdio.h>
#include <stdlib.h>

void main() {
  int *list, *ary;
  int i, x, p=0, num, max, sum;

  // input all numbers
  scanf("%d", &num);
  ary = (int*)malloc(sizeof(int) * num);
  list = (int*)malloc(sizeof(int) * num);
  for(i=0; i<num; i++) scanf("%d", list+i);

  // check if all numbers are not positive.
  // if so, find and print the maximum number
  for(i=0; i<num; i++){
    if(list[i] > 0) break;
  }
  if(i == num){
    max = list[0];
    for(i=1; i<num; i++){
      if(list[i] > max) max = list[i];
    }
    printf("%d", max);
    return;
  }

  // pre-processing
  ary[0] = 0;
  for(i=0; i<num; i++){
    x = list[i];
    if(x < 0){
      if(p&1) ary[p] += x;
      else ary[++p] = x;
    }else{
      if(p&1) ary[++p] = x;
      else ary[p] += x;
    }
  }

  // find the maximum sum
  max = sum = ary[0];
  i = 1;
  for(; i<p; i+=2){
    if(sum + ary[i] < 0){
      sum = ary[i+1];
    }else{
      sum += ary[i] + ary[i+1];
    }
    if(sum > max) max = sum;
  }

  // print the solution
  printf("%d", max);
  free(ary); free(list);
}


코드가 지저분한데 이 문제가 다시 생각나면 한 번 정리할 생각이다. 일단 떠오르는 걸로는 배열을 미리 압축하지 않아도 답을 구하는 데 문제가 없을 것 같다.
Comments