5. ๋ˆ„์  ํ•ฉ (Prefix Sums) Codility Lesson ํ•œ๊ตญ์–ด ์ •๋ฆฌ๋ณธ (JavaScript ver.)

๋ˆ„์  ํ•ฉ(Prefix Sums)์ด๋ž€?

๋ฐฐ์—ด์˜ ํŠน์ • ๊ตฌ๊ฐ„(์Šฌ๋ผ์ด์Šค)์˜ ํ•ฉ์„ ๋น ๋ฅด๊ฒŒ ๊ณ„์‚ฐํ•˜๋Š” ๊ฐ•๋ ฅํ•œ ๊ธฐ๋ฒ•์ด ๋ˆ„์  ํ•ฉ(Prefix Sums) ์ด๋‹ค. ์ด๋Š” ๋ฐฐ์—ด์˜ ์ฒ˜์Œ๋ถ€ํ„ฐ ํŠน์ • ์œ„์น˜๊นŒ์ง€์˜ ํ•ฉ์„ ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•ด ์ €์žฅํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ๋ฐฐ์—ด A๊ฐ€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค๊ณ  ํ•˜์ž.

A = [aโ‚€, aโ‚, aโ‚‚, ..., aโ‚™โ‚‹โ‚]

๊ทธ๋Ÿฌ๋ฉด ๋ˆ„์  ํ•ฉ ๋ฐฐ์—ด P๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜๋œ๋‹ค.

P[0] = 0
P[1] = aโ‚€
P[2] = aโ‚€ + aโ‚
P[3] = aโ‚€ + aโ‚ + aโ‚‚
...
P[n] = aโ‚€ + aโ‚ + ... + aโ‚™โ‚‹โ‚

์ด์ „ ๊ฐ’ P[k-1]์— ํ˜„์žฌ ๊ฐ’ A[k-1]์„ ๋”ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ˆ„์  ํ•ฉ์„ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ „์ฒด ์—ฐ์‚ฐ์€ O(n) ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.


1. O(n) ์‹œ๊ฐ„ ๋ณต์žก๋„์˜ ๋ˆ„์  ํ•ฉ ๊ณ„์‚ฐ

JavaScript ์ฝ”๋“œ:

function prefixSums(A) {
    let n = A.length;
    let P = new Array(n + 1).fill(0);
    for (let k = 1; k <= n; k++) {
        P[k] = P[k - 1] + A[k - 1];
    }
    return P;
}

์ด ํ•จ์ˆ˜๋Š” ์ž…๋ ฅ ๋ฐฐ์—ด A์˜ ๋ˆ„์  ํ•ฉ์„ ๊ณ„์‚ฐํ•˜์—ฌ ๋ฐ˜ํ™˜ํ•œ๋‹ค.


2. O(1) ์‹œ๊ฐ„ ๋ณต์žก๋„์˜ ๊ตฌ๊ฐ„ ํ•ฉ ๊ณ„์‚ฐ

๋ˆ„์  ํ•ฉ์„ ํ™œ์šฉํ•˜๋ฉด ํŠน์ • ๊ตฌ๊ฐ„ [x..y]์˜ ํ•ฉ์„ O(1) ๋งŒ์— ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

๊ตฌ๊ฐ„ ํ•ฉ: P[y + 1] - P[x]

JavaScript ์ฝ”๋“œ:

function countTotal(P, x, y) {
    return P[y + 1] - P[x];
}

์ด ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•˜๋ฉด O(n + m) ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ตฌ๊ฐ„ ํ•ฉ์„ ๋น ๋ฅด๊ฒŒ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค.


3. ๋ฒ„์„ฏ ์ค๊ธฐ ๋ฌธ์ œ

๋„๋กœ ์œ„ ํŠน์ • ์œ„์น˜ k์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ์ตœ๋Œ€ m๋ฒˆ ์ด๋™ํ•˜๋ฉด์„œ ๋ฒ„์„ฏ์„ ์ตœ๋Œ€ํ•œ ๋งŽ์ด ์ˆ˜์ง‘ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ด๋™์€ ์ธ์ ‘ํ•œ ์œ„์น˜๋กœ๋งŒ ๊ฐ€๋Šฅํ•˜๋‹ค.

O(nยฒ) (๋น„ํšจ์œจ์ ์ธ ๋ฐฉ๋ฒ•)

function slowMushrooms(A, k, m) {
    let n = A.length;
    let result = 0;
    for (let p = 0; p <= m; p++) {
        let left = k - p;
        let right = Math.min(n - 1, k + (m - 2 * p));
        let sum = 0;
        for (let i = left; i <= right; i++) {
            sum += A[i];
        }
        result = Math.max(result, sum);
    }
    return result;
}

์ด ๋ฐฉ๋ฒ•์€ O(mยฒ) ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค.


O(n + m) (ํšจ์œจ์ ์ธ ๋ฐฉ๋ฒ•)

๋ˆ„์  ํ•ฉ์„ ์ด์šฉํ•˜์—ฌ O(n + m) ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค.

function mushrooms(A, k, m) {
    let n = A.length;
    let result = 0;
    let P = prefixSums(A);
    
    for (let p = 0; p <= Math.min(m, k); p++) {
        let left = k - p;
        let right = Math.min(n - 1, Math.max(k, k + m - 2 * p));
        result = Math.max(result, countTotal(P, left, right));
    }
    
    for (let p = 0; p <= Math.min(m, n - k - 1); p++) {
        let right = k + p;
        let left = Math.max(0, Math.min(k, k - (m - 2 * p)));
        result = Math.max(result, countTotal(P, left, right));
    }
    
    return result;
}

์ด ๋ฐฉ๋ฒ•์€ ๋ˆ„์  ํ•ฉ์„ ํ™œ์šฉํ•˜์—ฌ ์Šฌ๋ผ์ด์Šค ํ•ฉ์„ O(1)์— ๊ณ„์‚ฐํ•˜๋ฏ€๋กœ ์ „์ฒด ์—ฐ์‚ฐ์„ O(n + m) ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋‹ค.

๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€