문제 설명
주어진 정수 배열 arr가 있을 때, 연속된 부분 배열의 합 중 최대 값을 구하는 문제입니다.
즉, arr의 연속된 몇 개의 숫자를 더했을 때 가장 큰 값이 무엇인지 찾아야 합니다.
이 문제는 자주 출제되는 코딩 테스트 문제 중 하나이며, Kadane의 알고리즘을 사용하여 해결할 수 있습니다.
문제 예시
입력
[2, -1, 3, 4, -2, 1, -5, 4]출력
10설명: 연속된 부분 배열 [3, 4, -2, 1]의 합이 최대인 10입니다.
문제 접근 방법
이 문제는 연속된 부분 배열의 합을 구하는 것이기 때문에 범위를 어떻게 설정할지가 관건입니다.
즉, 시작 지점과 끝 지점을 정하고 그 사이의 모든 원소를 더하는 방식으로 접근할 수 있지만,
이 방법은 비효율적입니다. 대신, Kadane의 알고리즘을 활용하여 O(n) 시간 복잡도로 해결할 수 있습니다.
Kadane의 알고리즘
Kadane의 알고리즘은 현재까지의 최대 연속 합과 현재 위치의 값을 비교하여 최대값을 갱신하는 방식으로 작동합니다.
구체적인 과정은 다음과 같습니다:
- 변수
maxSoFar와maxEndingHere를 초기화합니다. 둘 다 0 또는 배열의 첫 번째 요소로 초기화할 수 있습니다. - 배열을 순회하며 현재 값
arr[i]를maxEndingHere에 더합니다. maxEndingHere가maxSoFar보다 크면maxSoFar를 갱신합니다.- 만약
maxEndingHere가 0보다 작아지면 0으로 초기화하여 새로운 연속 합을 시작합니다.
이 방법은 배열 크기와 관계없이 O(n) 시간 내에 최대 합을 구할 수 있습니다.
코틀린 코드 구현
다음은 위의 알고리즘을 코틀린으로 구현한 코드입니다:
fun maxSubArraySum(arr: IntArray): Int {
var maxSoFar = arr[0]
var maxEndingHere = arr[0]
for (i in 1 until arr.size) {
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i])
maxSoFar = Math.max(maxSoFar, maxEndingHere)
}
return maxSoFar
}
fun main() {
val arr = intArrayOf(2, -1, 3, 4, -2, 1, -5, 4)
val result = maxSubArraySum(arr)
println("최대 연속 합: $result")
}
위 코드는 주어진 정수 배열에서 최대 연속 합을 구하는 함수 maxSubArraySum을 정의합니다.
시간 복잡도 분석
Kadane의 알고리즘은 한 번의 배열 순회를 통해 결과를 도출하기 때문에 시간 복잡도는 O(n)입니다.
따라서 배열의 크기가 커져도 성능에 큰 영향을 미치지 않습니다. 공간 복잡도는 O(1)이며 추가 데이터 구조를 사용하지 않기 때문에 매우 효율적입니다.
결론
연속 합 구하기 문제는 알고리즘 문제 풀이에서 빈번히 등장하는 문제로,
Kadane의 알고리즘을 통해 효율적으로 해결할 수 있습니다. 이를 통해 코틀린의 기본 문법과 알고리즘 설계를 동시에 학습할 수 있습니다.
코딩 테스트에서 종종 출제되는 문제이므로 연습하여 자연스럽게 구현할 수 있도록 하십시오.
추가 연습 문제
다음의 변형 문제들을 통해 추가적인 연습을 해보세요:
- 주어진 배열에서 연속된 부분 배열의 시작 인덱스와 끝 인덱스를 함께 출력하는 프로그램을 작성하라.
- 모든 원소가 음수인 배열을 입력으로 받았을 때의 최대 연속 합을 구하라.
- 여러 개의 테스트 케이스를 입력 받아 그에 대한 최대 연속 합을 출력하는 프로그램을 만들어라.