[동적 계획법] Kadane’s Algorithm (카데인 알고리즘)

카데인 알고리즘이란?

카데인 알고리즘(Kadane’s Algorithm)은 연속된 부분 배열의 최대 합을 찾을 때 사용된다. 주로 배열이나 리스트에서 연속된 원소들의 합이 최대가 되는 부분 배열을 효율적으로 찾는 경우에 유용하다.

예를 들어, 주어진 배열의 각 원소가 양수, 음수, 또는 0일 때 그 배열에서 연속적인 부분 배열의 최대 합을 구하고자 할 때 카데인 알고리즘을 사용하면 O(n)의 시간 복잡도로 문제를 해결하며, 동적 계획법(Dynamic Programming) 접근법을 사용한다. 이 알고리즘은 매 반복마다 현재 부분 합과 최대 부분 합을 갱신해 가며 최적의 해답을 찾아가는 방식이다.

 

카데인 알고리즘의 원리

카데인 알고리즘은 현재까지의 최대 부분 배열의 합을 유지하면서, 각 요소를 순차적으로 탐색한다. 카데인 알고리즘은 아래의 두 가지 값을 유지한다.

현재 위치에서 끝나는 최대 합 (max_ending_here) : 현재 위치에서 끝나는 부분 배열 중 최대 합
현재까지의 최대 합 (max_so_far) : 지금까지 발견한 최대 부분 배열의 합

 

의사코드

1	max_so_far와 max_ending_here를 배열의 첫 번째 요소로 초기화한다.
2	배열의 두 번째 요소부터 순차적으로 탐색한다.
3	각 요소마다 max_ending_here를 업데이트한다. (max_ending_here = max(array[i], max_ending_here + array[i]))
4	max_so_far를 현재 max_ending_here와 비교하여 더 큰 값을 저장한다. (max_so_far = max(max_so_far, max_ending_here))
5	배열의 끝까지 탐색한 후 max_so_far를 반환한다.

 

코드

public class KadaneAlgorithm {
    // 카데인 알고리즘을 구현하는 함수
    public static int kadaneAlgorithm(int[] array) {
        // 배열의 첫 번째 요소로 초기화
        int maxSoFar = array[0];
        int maxEndingHere = array[0];
        
        // 배열의 두 번째 요소부터 탐색
        for (int i = 1; i < array.length; i++) {
            // 현재 요소를 포함하여 최대 합을 구함
            maxEndingHere = Math.max(array[i], maxEndingHere + array[i]);
            // 현재까지의 최대 합을 갱신
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        
        return maxSoFar;
    }

    // 메인 함수
    public static void main(String[] args) {
        int[] array = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("최대 부분 배열 합: " + kadaneAlgorithm(array));
    }
}

 

알고리즘 사용 예시

1.주식 가격 변화에서 특정 구간 동안의 최대 수익을 구할 때
2.게임 점수 기록에서 최대 점수를 낼 수 있는 연속 구간을 찾을 때
3.데이터 분석에서 연속적인 데이터를 분석하며 최대값 구간을 찾을 때

 

참고자료

[1] fubabaz 티스토리