코틀린 코딩테스트 강좌, 연속 합 구하기

문제 설명

주어진 정수 배열 arr가 있을 때, 연속된 부분 배열의 합 중 최대 값을 구하는 문제입니다.
즉, arr의 연속된 몇 개의 숫자를 더했을 때 가장 큰 값이 무엇인지 찾아야 합니다.
이 문제는 자주 출제되는 코딩 테스트 문제 중 하나이며, Kadane의 알고리즘을 사용하여 해결할 수 있습니다.

문제 예시

입력

[2, -1, 3, 4, -2, 1, -5, 4]

출력

10

설명: 연속된 부분 배열 [3, 4, -2, 1]의 합이 최대인 10입니다.

문제 접근 방법

이 문제는 연속된 부분 배열의 합을 구하는 것이기 때문에 범위를 어떻게 설정할지가 관건입니다.
즉, 시작 지점과 끝 지점을 정하고 그 사이의 모든 원소를 더하는 방식으로 접근할 수 있지만,
이 방법은 비효율적입니다. 대신, Kadane의 알고리즘을 활용하여 O(n) 시간 복잡도로 해결할 수 있습니다.

Kadane의 알고리즘

Kadane의 알고리즘은 현재까지의 최대 연속 합과 현재 위치의 값을 비교하여 최대값을 갱신하는 방식으로 작동합니다.
구체적인 과정은 다음과 같습니다:

  1. 변수 maxSoFar와 maxEndingHere를 초기화합니다. 둘 다 0 또는 배열의 첫 번째 요소로 초기화할 수 있습니다.
  2. 배열을 순회하며 현재 값 arr[i]를 maxEndingHere에 더합니다.
  3. maxEndingHere가 maxSoFar보다 크면 maxSoFar를 갱신합니다.
  4. 만약 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의 알고리즘을 통해 효율적으로 해결할 수 있습니다. 이를 통해 코틀린의 기본 문법과 알고리즘 설계를 동시에 학습할 수 있습니다.
코딩 테스트에서 종종 출제되는 문제이므로 연습하여 자연스럽게 구현할 수 있도록 하십시오.

추가 연습 문제

다음의 변형 문제들을 통해 추가적인 연습을 해보세요:

  • 주어진 배열에서 연속된 부분 배열의 시작 인덱스와 끝 인덱스를 함께 출력하는 프로그램을 작성하라.
  • 모든 원소가 음수인 배열을 입력으로 받았을 때의 최대 연속 합을 구하라.
  • 여러 개의 테스트 케이스를 입력 받아 그에 대한 최대 연속 합을 출력하는 프로그램을 만들어라.

참고 자료