위키백과, 지식백과, 나무위키 등을 뒤져봤지만 카데인 알고리즘에 대한 공식 문서는 찾을 수 없었다.

알고리즘 전공 서적 정도는 구매해야 확인해볼 수 있나보다..😓

13398번: 연속합 2 이 문제를 풀다가 어려움을 느껴서 제대로 공부해야겠다는 생각이 들었다.

이 문제는 카데인 알고리즘에다가 DP 방식까지 적용해야 풀리는데, 문제는 카데인 알고리즘만을 적용해서 푸는 방식도 잘 생각이 나지 않았다..

1912번: 연속합 이 문제가 정확히 카데인 알고리즘만을 사용해서 풀 수 있는 문제다.

카데인 알고리즘 (Kadane's Algorithm) 어디에 써먹는데?

우선 카데인 알고리즘이 무엇인지부터 알아보자.

카데인 알고리즘이란 1차원 배열 내에서 연속된 하위 배열의 원소들의 합이 가장 큰 경우를 찾는 동적 계획법 기반의 효율적인 알고리즘이다.

즉, 쉽게 말해 배열 내에서 가장 큰 구간합을 구하는 알고리즘이란 말이다. 다른 말로는 최대 하위 배열 합 문제(Maximum Subarray Sum Problem)이라고 한단다.

1912번: 연속합 이 문제에서 정확히 수열 하나를 주고, 그 중에서 구간합의 최댓값을 구하라고 했으니 카데인 알고리즘을 사용해서 푸는 문제다.

문제에서는 이러한 입력이 주어진다.

10
10 -4 3 1 5 6 -35 12 21 -1

투 포인터로 풀 수 있는 거 아니야?

문제를 처음 봤을 때 "투 포인터로 풀면 되지 않을까?" 라는 생각이 들기도 했다.

왜냐면 결국에 모든 구간을 살펴보되, 해당 음수를 포함할지 말지를 다 따져봐야 하니
구간합을 계속 기억하면서 수열의 끝까지 살펴보면 되지 않을까 라는 생각이었다.

음수를 만났더라도 그 뒤에 만나는 양수들을 더하다보면 최댓값을 갱신할 수도 있기에 그럴 경우에는 Right를 계속 증가시키고,
너무 큰 음수를 만나서 더하지 않는 게 낫다고 판단되는 경우에는 Left를 현재의 위치로 증가시키는 것이다.

하지만 투 포인터는 시간 복잡도가 O(N^2)이기 때문에 그렇게 효율적이지는 않다.

이렇게 생각했던 부분이 카데인 알고리즘과 거의 유사하다.

음수를 만났을 때, 언제 그 값을 사용해야할까?

특정 음수를 만났을 때 그 값을 채택할지, 말지 여부를 결정해야 한다.

근데 그 값을 채택하는 경우는 어떤 경우일까?

10
10 -4 3 1 5 6 -35 12 21 -1

여기서 -4를 살펴보자.

-4는 더하는 것이 유리할까? 더하지 않는 것이 유리할까?
즉, -4를 포함하는 구간합이 클까? 포함하지 않는 구간합이 더 클까?

-4의 왼쪽의 양수들을 보면 10이 있고,
오른쪽의 양수들을 보면 15(3 1 5 6)가 있다.

양쪽 중에 하나라도 -4보다 큰 값을 가진다면 그럴 때는 -4를 구간합에 포함시키는 게 유리하다

반면에 -35를 보면 양쪽 어느 곳도 -35보다 크지 않다.

그래서 -35는 포함시키는 않는 것이 유리하다.

그런데 이건 양쪽의 수를 끝까지 보고 판단해야 한다는 단점이 존재한다.

카데인 알고리즘

카데인 알고리즘을 이해하면, 음수를 만났을 때 기존의 누적값을 계속 사용할지 말지를 결정할 수 있다.

음수를 만났을 때, 기존 누적합에 새로 만난 음수를 더한 값과
음수만으로 누적합을 새로 시작하는 것 중에서
더 큰 것을 채택하는 것이다.

그리고 이건 사실 양수를 만났을 때도 마찬가지다.

기존의 누적합이 음수였다면, 누적값을 버리고 양수로 새로 누적합을 계산하는 게 더 클 것이다.

즉, 새로운 값을 만났을 때,
그것까지 더한 누적합과
새로운 값 중에서 더 큰 값으로 누적합을 계속 갱신하는 것이다.

그리고 그러한 과정에서 최댓값 변수도 따로 만들어서 갱신하면 된다.

그래서 우리가 기억해야할 변수는 두 가지다.

현재까지의 누적합과 전체 구간의 최댓값이다.

그것을 각각 Prefix Sum과 global_max이라 하고 아래와 같이 점화식을 세울 수 있다.

Prefix Sum = max(Prefix Sum + new value, new value)
answer = max(answer, Prefix Sum)

표로 과정을 살펴보면 이렇다.

현재 원소 (num)	Prefix Sum 계산	새로운 Prefix Sum	global_max 계산	새로운 global_max
10	10(초기값)	10	10(초기값)	10
-4	max(10 + (-4), -4)	6	max(6, 10)	10
3	max(6 + 3, 6)	9	max(9, 10)	10
1	max(9 + 1, 9)	10	max(10, 10)	10
5	max(9 + 5, 9)	14	max(14, 10)	14
6	max(14 + 6, 6)	20	max(20, 14)	20
-35	max(20 + (-35), -35)	-15	max(-15, 20)	20
12	max(-15 + 12, 12)	12	max(12, 20)	20
21	max(12 + 21, 21)	33	max(33, 20)	33
-1	max(33 + (-1), -1)	32	max(32, 33)	33

코드는 이렇다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 배열 입력 받기
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 탐색
        int sum = arr[0], maxSum = arr[0];
        for (int i = 1; i < N; i++) {
            sum = Math.max(arr[i], sum + arr[i]);
            maxSum = Math.max(sum, maxSum);
        }

        // 출력
        System.out.println(maxSum);
    }
}

막상 이해하고 나서 코드로 보면 되게 간단한데, 풀 때는 저런 생각이 쉽게 나지 않았다..😓