카데인 알고리즘이란?
카데인 알고리즘(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.데이터 분석에서 연속적인 데이터를 분석하며 최대값 구간을 찾을 때
