ASPP - 4.9. 부분 구간 최대 합

• 개요
  • 풀이법
    • 브루트 포스: $O(N^{3})$
    • $O(N^{2})$
    • 분할 정복: $O(N\log{N})$
    • 동적 계획법: $O(N)$
  • 비교
  • 알고리즘 따른 처리량과 속도

개요

• 부분 구간 중 그 합이 최대인 구간을 찾는 문제
• 가령 [-7, 4, -3, 6, 3, -8, 3, 4]에서 [4, -3, 6, 3]의 합이 가장 크다

풀이법

브루트 포스: $O(N^{3})$

private static final int MIN = Integer.MIN_VALUE; /* -2^31 = -2147483648 */

/**
  * 주어진 배열의 모든 부분 구간을 순회하며 그 합을 계산
  * - O(N^3) 복잡도
  */
public int inefficientMaxSum(int[] A) {
    int N = A.length;
    int answer = MIN;
    for (int i = 0; i < N; i++) { /* 전체 배열 순회 */
        for (int j = i; j < N; j++) { /* 배열의 일부 구간을 순회 */
            /* A[i..j] 구간의 합을 구한다*/
            int sum = 0;
            for (int k = i; k <= j; k++) {/* 구간별로 하나 하나 더하고 */
                sum += A[k];
            }
            answer = Math.max(sum, answer); /* 구간별로 합을 비교한다 */
        }
    }

    return answer;
}

• $O(N^{2})$ 개의 가능한 구간 검사 $\times$ $O(N)$ 구간 합 = $O(N^{3})$
• 하지만 굳이 반복문을 돌면서 합을 구할 필요가 있을까? 이동평균선처럼 반복문 하나를 줄일 수 있다.

$O(N^{2})$

/**
* 일정 범위의 계산된 값 재사용하는 이동평균선 개선 방식 적용
* @param A 숫자 구간을 담고있는 배열
* @return
*/
public int betterMaxSum(int[] A) {
    int N = A.length;
    int answer = MIN;
    for (int i = 0; i < N; i++) { /* 전체 배열 순회 */
        int sum = 0;
        for (int j = i; j < N; j++) { /* 배열의 일부 구간을 순회 */
            /* 그냥 모두 더해가면서 최대값이 되는 값을 반환한다 */
            sum += A[j]; // 매번 반복문 돌 필요 없다. 최대값이 되는 어떤 A[i..j]의 max 값이 answer 변수에 담긴다
            answer = Math.max(sum, answer);
        }
    }

    return answer;
}

• sum += A[j]는 구간을 도는 김에 같이 더해버린다.
• $O(N^{3})$에서처럼 굳이 더하는 것을 반복문 돌면서 할 필요가 없다. 각 구간을 순회하며 모두 더하면 된다
• 가령 [-7, 4, -3, 6, 3, -8, 3, 4]에서,
  • i = 0
    • -7: -7 = -7
    • -3: -7 + 4 = -3
    • -3: -7 + 4 - 3 = -6
    • 0: -7 + 4 - 3 + 6 = 0
    • 3: -7 + 4 - 3 + 6 + 3 = 3
    • 3: -7 + 4 - 3 + 6 + 3 - 8 = -5
    • 3: -7 + 4 - 3 + 6 + 3 - 8 + 3 = -2
    • 3: -7 + 4 - 3 + 6 + 3 - 8 + 3 + 4 = 2
  • i = 1
    • 4: 4 = 4
    • 4: 4 - 3 = 1
    • 7: 4 - 3 + 6 = 7
    • 10: 4 - 3 + 6 + 3 = 10 <- 최대값이 되는 부분
    • 이하 생략

분할 정복: $O(N\log{N})$

/**
* 분할 정복 기법
* - O(N lg N)
* @param A
* @param lo
* @param hi
* @return
*/
public int fastMaxSum(int[] A, int lo, int hi) {
    /* 기저 사례: 구간의 길이가 1일 경우 */
    if (lo == hi) return A[lo];
    /* (lo + hi)에서 오버플로 발생 가능하므로 `가장 작은 값 + 절반`으로 중앙값을 구한다 */
    int mid = lo + (hi - lo) / 2;
    int left = MIN;
    int sum = 0;
    /* 중앙을 기점으로 해서 좌/우로 퍼져나가며 max값을 구해 나간다. 그럼 좌/우 각각의 최대값을 구할 수 있고 */
    for (int i = mid; i >= lo; i--) {
        sum += A[i];
        left = Math.max(left, sum);
    }
    int right = MIN;
    sum = 0;
    for (int j = mid + 1; j <= hi; j++) {
        sum += A[j];
        right = Math.max(right, sum);
    }

    /* 다시 중앙을 기점으로 좌/우 배열을 나눠서 더 작은 단위의 배열에서 검증한다 */
    int leftSideMaxSum = fastMaxSum(A, lo, mid);
    int rightSideMaxSum = fastMaxSum(A, mid + 1, hi);
    int comparedLeftAndRightSideMaxSum = Math.max(leftSideMaxSum, rightSideMaxSum);

    /* 앞서 `좌/우로 퍼져나가는 것` vs `좌/우 배열을 더 작은 단위로 나눈 것` 두 가지를 비교해서 더 큰 값을 반환한다 */
    return Math.max(left + right, comparedLeftAndRightSideMaxSum);
}

• 재귀호출, 탐욕법을 이용해 계산

동적 계획법: $O(N)$

/**
* 동적 계획법
* A[i]를 우측 끝으로 갖는 구간의 최대합 반환 함수 = maxAt(i)
* 1. A[i] 단일
* 2. ... + A[i-2] + A[i-1] = 최대합. 여기에 A[i]를 더한다
* => maxAt(i) = max(0, maxAt(i - 1)) + A[i]
* 좌측 0에서부터 우측으로 이동하면서 A[i]를 더해가며 가장 큰 값을 찾는다
* @param A
* @return
*/
public int fastestMaxSum(int[] A) {
    int N = A.length;
    int answer = MIN;
    int partialSum = 0;
    for (int i = 0; i < N; i++) {
        /* 이동평균선 개선처럼 부분 합을 유지하되, 이전 구간까지의 합이 0보다 작다면 계속 A[i]부터 다시 시작한다 */
        partialSum = Math.max(partialSum, 0) + A[i]; 
        answer = Math.max(answer, partialSum);
    }

    return answer;
}

• 다 그렇겠지만, 동적 계획법은 개인적으로 가장 잘 다루고 싶은 알고리즘이다. 간결한데 빠르다니 최고다.
• 점화식을 구한다
  • 구간이라 함은 시작과 끝이 있고,
  • 더 작은 구간에 끝을 더해나간다고 볼 수 있다
    • A[i]
    • A[i-1] + A[i]
    • A[i-2] + A[i-1] + A[i]
  • 그럼 이를 이전 구간의 최대 합을 반환하는 함수로 추상화할 수 있다
    • 임의의 수식, 그러니까 마음대로 어떤 i 지점에서 최대가 되는 합을 반환하는 함수를 maxAt(i)라고 해보다
    • 그럼 이전 최대 구간의 합을 구하는 함수는? maxAt(i-1)이 된다
    • 그럼 어디선가 시작점을 바꾸는 부분이 필요한데? 그것을 이전 구간 최대 합과 0을 비교하면서,
      • 이전 구간 최대 합이 0보다 작으면 0 + A[i]가 되어 A[i]부터 구간이 다시 시작된다
      • 이전 구간 최대 합이 0보다 크다면 이전 구간 최대 합 + A[i]를 partialSum 변수에 저장

비교

[-7, 4, -3, 6, 3, -8, 3, 4]
inefficientMaxSum: 10
Execution time in nanoseconds: 331401
betterMaxSum: 10
Execution time in nanoseconds: 135300
fastMaxSum: 10
Execution time in nanoseconds: 85199
fastestMaxSum: 10
Execution time in nanoseconds: 124200

[-7, 10, 4, 33, 3, -10, -3, 4, 7, -3, 6, -1, -20, 3, -8, 3, 4, 40, 6, -3, -2, -9, -22, 60, -2, 80, 30, 100, -89, -32, -111, 90]
inefficientMaxSum: 310
Execution time in nanoseconds: 374501
betterMaxSum: 310
Execution time in nanoseconds: 144701
fastMaxSum: 310
Execution time in nanoseconds: 143999
fastestMaxSum: 310
Execution time in nanoseconds: 129299
==========================test <com.algo.apss.ch4.MaxSum> done==========================

• 하지만 항상 동적 계획법이 더 빠른 건 아니다.
• 원소의 수가 적다면 오히려 분할 정복 기법을 사용한 fastMaxSum가 더 빠르다
• 하지만 BigO 표기법에서 O(N)이 가지는 장점은 원소가 커질수록 훨씬 빨라진다는 것

알고리즘 따른 처리량과 속도

알고리즘	1초 내 처리 가능량	반복 수
$O(N^{3})$	2,560	$2,560^{3}$ = 16,777,216,000
$O(N^{2})$	40,960	$40,960^{2}$ = 1,677,721,600
$O(N\log{N})$	20,000,000	$20,000,000\log{20,000,000}$ = 약 485,069,933
$O(N)$	160,000,000	160,000,000