콘텐츠로 이동

최대/최소 합을 갖는 부분 배열 찾기

여기서는 최대 합을 갖는 부분 배열을 찾는 문제와 함께 몇 가지 변형 문제(이 문제를 온라인으로 해결하는 알고리즘 포함)를 살펴봅니다.

문제 설명

수로 이루어진 배열 $a[1 \ldots n]$이 주어집니다. 합이 최대인 부분 배열 $a[l \ldots r]$을 찾아야 합니다:

$$ \max_{ 1 \le l \le r \le n } \sum_{i=l}^{r} a[i].$$

예를 들어, 배열 $a[]$의 모든 정수가 음이 아니라면 답은 배열 전체가 됩니다. 그러나 배열에 양수와 음수가 모두 포함될 수 있는 경우에는 해법이 자명하지 않습니다.

최소 부분 배열을 찾는 문제도 본질적으로 같다는 것은 분명합니다. 모든 수의 부호만 바꾸면 됩니다.

알고리즘 1

여기서는 거의 자명한 알고리즘을 살펴봅니다. (그다음에는 떠올리기는 조금 더 어렵지만 구현은 훨씬 더 짧은 다른 알고리즘을 살펴보겠습니다.)

알고리즘 설명

이 알고리즘은 매우 간단합니다.

편의를 위해 다음 표기법을 도입합니다: $s[i] = \sum_{j=1}^{i} a[j]$. 즉, 배열 $s[i]$는 배열 $a[]$의 부분합 배열입니다. 또한 $s[0] = 0$으로 둡니다.

이제 인덱스 $r = 1 \ldots n$을 순회하면서, 현재의 각 $r$ 값에 대해 부분 배열 $[l, r]$에서 최대 합이 되게 하는 최적의 $l$을 빠르게 찾는 방법을 알아봅시다.

형식적으로 말하면, 현재의 $r$에 대해 $s[r] - s[l-1]$의 값이 최대가 되도록 하는 ($r$을 넘지 않는) $l$을 찾아야 한다는 뜻입니다. 간단한 변형을 거치면, 배열 $s[]$에서 구간 $[0, r-1]$의 최솟값을 찾아야 한다는 것을 알 수 있습니다.

여기서 곧바로 해법을 얻을 수 있습니다: 배열 $s[]$에서 현재 최솟값이 어디에 있는지를 저장해 두기만 하면 됩니다. 이 최솟값을 이용하면 현재의 최적 인덱스 $l$을 $O(1)$에 찾을 수 있고, 현재 인덱스 $r$에서 다음 인덱스로 넘어갈 때는 이 최솟값을 갱신하기만 하면 됩니다.

이 알고리즘은 분명히 $O(n)$에 동작하며 점근적으로 최적입니다.

구현

이를 구현할 때는 부분합 배열 $s[]$를 명시적으로 저장할 필요조차 없습니다 — 그중 현재 원소만 있으면 됩니다.

구현은 위에서 설명한 1부터 시작하는 번호 매기기가 아니라 0부터 시작하는 인덱스의 배열로 제시합니다.

먼저 원하는 구간의 인덱스는 찾지 않고 단순히 수치로 된 답만 구하는 해법을 제시합니다:

int ans = a[0], sum = 0, min_sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum - min_sum);
    min_sum = min(min_sum, sum);
}

이제 원하는 구간의 경계까지 추가로 찾는 해법의 완전한 버전을 제시합니다:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, min_sum = 0, min_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    int cur = sum - min_sum;
    if (cur > ans) {
        ans = cur;
        ans_l = min_pos + 1;
        ans_r = r;
    }
    if (sum < min_sum) {
        min_sum = sum;
        min_pos = r;
    }
}

알고리즘 2

여기서는 다른 알고리즘을 살펴봅니다. 이해하기는 조금 더 어렵지만, 위의 알고리즘보다 더 우아하고 구현도 조금 더 짧습니다. 이 알고리즘은 1984년에 Jay Kadane이 제안했습니다.

알고리즘 설명

알고리즘 자체는 다음과 같습니다. 배열을 차례로 훑으면서 현재까지의 부분합을 어떤 변수 $s$에 누적해 갑시다. 어느 시점에 $s$가 음수가 되면, 그냥 $s=0$을 대입합니다. 알고리즘이 진행되는 동안 변수 $s$에 대입되는 모든 값 중 최댓값이 문제의 답이 된다고 주장할 수 있습니다.

증명:

$s$의 합이 처음으로 음수가 되는 인덱스를 생각해 봅시다. 이는 부분합 0에서 시작하여 결국 음수인 부분합을 얻었다는 뜻이므로, 배열의 이 접두사 전체뿐 아니라 그 어떤 접미사도 합이 음수입니다. 따라서 이 부분 배열은 자신을 접두사로 갖는 어떤 부분 배열의 부분합에도 결코 도움이 되지 않으며, 그냥 버려도 됩니다.

하지만 이것만으로는 알고리즘을 증명하기에 충분하지 않습니다. 이 알고리즘에서 우리는 실제로 $s<0$이 발생한 위치 바로 다음에서 시작하는 구간들로만 답의 탐색 범위를 제한하고 있습니다.

그런데 실제로 임의의 구간 $[l, r]$을 생각해 보고, $l$이 그러한 "임계" 위치에 있지 않다고 합시다(즉, $p$가 $s<0$이 된 마지막 위치일 때 $l > p+1$입니다). 마지막 임계 위치가 $l-1$보다 엄밀히 앞에 있으므로, $a[p+1 \ldots l-1]$의 합은 음수가 아님을 알 수 있습니다. 이는 $l$을 위치 $p+1$로 옮기면 답이 커지거나, 극단적인 경우에도 변하지 않는다는 뜻입니다.

어느 쪽이든, 답을 탐색할 때 $s<0$이 나타난 위치 바로 다음에서 시작하는 구간들로만 범위를 제한해도 된다는 것을 알 수 있습니다. 이로써 알고리즘이 올바름이 증명됩니다.

구현

알고리즘 1에서와 마찬가지로, 먼저 원하는 구간의 경계는 구하지 않고 수치로 된 답만 구하는 간단한 구현을 제시합니다:

int ans = a[0], sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum);
    sum = max(sum, 0);
}

해당 구간의 경계 인덱스까지 유지하는 완전한 풀이입니다:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, minus_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    if (sum > ans) {
        ans = sum;
        ans_l = minus_pos + 1;
        ans_r = r;
    }
    if (sum < 0) {
        sum = 0;
        minus_pos = r;
    }
}

제약 조건이 있는 최대/최소 부분 배열 찾기

문제 조건이 구하려는 구간 $[l, r]$에 추가 제약을 부과하는 경우(예를 들어 구간의 길이 $r-l+1$이 지정된 범위 안에 있어야 하는 경우), 설명한 알고리즘은 이러한 경우로도 쉽게 일반화될 가능성이 높습니다 — 어쨌든 문제는 여전히 지정된 추가 제약 하에서 배열 $s[]$의 최솟값을 찾는 것이 됩니다.

문제의 2차원 버전: 최대/최소 부분 행렬 찾기

이 글에서 설명한 문제는 더 높은 차원으로 자연스럽게 일반화됩니다. 예를 들어 2차원에서는 주어진 행렬에서 원소들의 합이 최대가 되는 부분 행렬 $[l_1 \ldots r_1, l_2 \ldots r_2]$를 찾는 문제가 됩니다.

1차원 버전의 풀이를 이용하면 2차원 버전에 대한 $O(n^3)$ 풀이를 쉽게 얻을 수 있습니다: $l_1$과 $r_1$의 가능한 모든 값을 순회하면서, 행렬의 각 행에서 $l_1$부터 $r_1$까지의 합을 계산합니다. 이제 이 배열에서 인덱스 $l_2$와 $r_2$를 찾는 1차원 문제가 남으며, 이는 이미 선형 시간에 풀 수 있습니다.

이 문제를 푸는 더 빠른 알고리즘들이 알려져 있지만, $O(n^3)$보다 크게 빠르지는 않으며 매우 복잡합니다(너무 복잡해서 그중 상당수는 숨겨진 상수 때문에 모든 현실적인 제약 조건에서 자명한 알고리즘보다 성능이 떨어집니다). 현재 알려진 가장 좋은 알고리즘은 $O\left(n^3 \frac{ \log^3 \log n }{ \log^2 n} \right)$ 시간에 동작합니다(T. Chan 2007 "가중치 그래프에서 모든 쌍 최단 경로를 구하는 더 많은 알고리즘")

Chan의 이 알고리즘은 이 분야의 다른 많은 결과와 마찬가지로 실제로는 빠른 행렬 곱셈을 다룹니다(여기서 행렬 곱셈이란 변형된 곱셈을 의미합니다: 덧셈 대신 최솟값을, 곱셈 대신 덧셈을 사용합니다). 합이 최대인 부분 행렬을 찾는 문제는 모든 정점 쌍 사이의 최단 경로를 찾는 문제로 환원될 수 있으며, 이 문제는 다시 이러한 행렬 곱셈으로 환원될 수 있습니다.

평균이 최대/최소인 부분 배열 찾기

이 문제는 평균값이 최대가 되는 구간 $a[l, r]$을 찾는 것입니다:

$$ \max_{l \le r} \frac{ 1 }{ r-l+1 } \sum_{i=l}^{r} a[i].$$

물론 구하려는 구간 $[l, r]$에 다른 조건이 전혀 없다면, 해는 항상 배열의 최대 원소 하나로 이루어진 길이 $1$의 구간이 됩니다. 이 문제는 추가 제약이 있을 때만 의미가 있습니다(예를 들어 구하려는 구간의 길이에 하한이 있는 경우).

이 경우 평균값 문제를 다룰 때 사용하는 표준 기법을 적용합니다. 즉, 원하는 최대 평균값을 이진 탐색으로 선택합니다.

이렇게 하려면 다음 부분 문제를 푸는 방법을 알아야 합니다. 수 $x$가 주어졌을 때, 배열 $a[]$에 평균값이 $x$보다 큰 부분 배열(물론 문제의 추가 제약을 모두 만족하는 것)이 있는지 확인해야 합니다.

이 부분 문제를 풀려면 배열 $a[]$의 각 원소에서 $x$를 뺍니다. 그러면 이 부분 문제는 사실상 이 배열에 합이 양수인 부분 배열이 있는지 없는지를 묻는 문제가 됩니다. 그리고 이 문제를 푸는 방법은 이미 알고 있습니다.

따라서 점근 복잡도가 $O(T(n) \log W)$인 해를 얻습니다. 여기서 $W$는 요구되는 정밀도이고, $T(n)$은 길이 $n$인 배열에 대해 부분 문제를 푸는 시간입니다(이 시간은 부과된 구체적인 추가 제약에 따라 달라질 수 있습니다).

온라인 문제 풀이

문제의 조건은 다음과 같습니다. $n$개의 수로 이루어진 배열과 수 $L$이 주어집니다. $(l,r)$ 형태의 쿼리가 주어지며, 각 쿼리마다 구간 $[l, r]$ 안에서 길이가 $L$ 이상이고 산술 평균이 가장 큰 부분 배열을 찾아야 합니다.

이 문제를 푸는 알고리즘은 상당히 복잡합니다. KADR(Yaroslav Tverdokhleb)는 러시아 포럼에서 자신의 알고리즘을 설명했습니다.