9. 최대 슬라이스 문제 (Maximum Slice Problem) Codility Lesson 한국어 정리본 (JavaScript ver.)

    최대 슬라이스 문제란?

    주어진 정수 배열 A = [a₀, a₁, ..., aₙ₋₁] 에서 연속된 부분 배열(슬라이스, Slice) 중 합이 최대가 되는 구간을 찾는 문제 이다. 즉, 두 인덱스 p, q (p ≤ q)를 선택하여 A[p] + A[p+1] + ... + A[q] 값이 최대가 되는 경우 를 찾는다.

    예를 들어, 다음과 같은 배열이 있을 때:

    A = [5, -7, 3, 5, -2, 4, -1];
    

    위 배열에서 최대 합을 갖는 부분 배열은 [3, 5, -2, 4]이며, 합은 10이다.


    1. O(n³) 시간 복잡도의 비효율적인 방법

    모든 가능한 슬라이스를 탐색하여 최댓값을 찾는 방법이다.

    JavaScript 코드:

    function slowMaxSlice(A) {
        let n = A.length;
        let result = 0;
        
        for (let p = 0; p < n; p++) {
            for (let q = p; q < n; q++) {
                let sum = 0;
                for (let i = p; i <= q; i++) {
                    sum += A[i];
                }
                result = Math.max(result, sum);
            }
        }
        return result;
    }
    

    시간 복잡도: O(n³) (모든 가능한 슬라이스를 반복 탐색)


    2. O(n²) 시간 복잡도의 개선된 방법

    누적 합(Prefix Sums)을 이용하면 O(n²) 로 개선할 수 있다.

    JavaScript 코드:

    function quadraticMaxSlice(A) {
        let n = A.length;
        let result = 0;
        
        for (let p = 0; p < n; p++) {
            let sum = 0;
            for (let q = p; q < n; q++) {
                sum += A[q];
                result = Math.max(result, sum);
            }
        }
        return result;
    }
    

    시간 복잡도: O(n²) (부분합을 저장하여 중복 계산 제거)


    3. O(n) 시간 복잡도의 최적화된 방법 (카데인 알고리즘)

    아이디어:

    • maxEnding 변수에 현재까지의 최대 종료 부분합 을 저장.
    • 다음 원소를 추가했을 때, maxEnding 이 양수이면 그대로 더하고, 음수이면 0으로 초기화.
    • 전체 배열에서 가장 큰 maxEnding 값을 반환.

    JavaScript 코드:

    function goldenMaxSlice(A) {
        let maxEnding = 0;
        let maxSlice = 0;
        
        for (let a of A) {
            maxEnding = Math.max(0, maxEnding + a);
            maxSlice = Math.max(maxSlice, maxEnding);
        }
        
        return maxSlice;
    }
    

    시간 복잡도: O(n) (한 번의 루프만 수행)

     

     

    하지만 위의 코드는 모든 배열의 값이 음수일 경우, 잘못된 결과를 반환할 수 있으므로, 올바른 코드는 

    function goldenMaxSlice(A) {
        let maxEnding = A[0];
        let maxSlice = A[0];
        
        for (let i = 1; i < A.length; i++) {
            // Either start a new slice at A[i] or continue the previous one
            maxEnding = Math.max(A[i], maxEnding + A[i]);
            maxSlice = Math.max(maxSlice, maxEnding);
        }
        
        return maxSlice;
    }
    반응형

    댓글