๐Ÿงฎ ์•Œ๊ณ ๋ฆฌ์ฆ˜ : ๋ˆ„์ ํ•ฉ (Prefix sum)

time-limit-exceeded.png ! TIME LIMIT EXCEEDED !

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€๋‹ค๋ณด๋ฉด ๋‹จ์ˆœํžˆ ๋ฐ˜๋ณต ์ˆ˜ํ–‰ํ•˜๋ฉด ์‹œ๊ฐ„ ์ดˆ๊ณผ์— ๊ฑธ๋ฆฌ๊ฒŒ ๋˜๋Š” ์œ ํ˜•์˜ ๋ฌธ์ œ๊ฐ€ ๋งŽ์ด ๋‚˜ํƒ€๋‚ฉ๋‹ˆ๋‹ค. ์š”๊ตฌํ•˜๋Š” ๊ฒฐ๊ณผ๋ฅผ ์ฐพ๋Š” ๋กœ์ง์„ ์—ด์‹ฌํžˆ ๊ตฌํ˜„ํ•œ ๋’ค์— โ€œ์˜ค ๋“œ๋””์–ด ๊ตฌํ•ด์ง„๋‹ค!โ€ ํ•˜๊ณ  ์ œ์ถœํ–ˆ๋Š”๋ฐ, ์‹œ๊ฐ„ ์ดˆ๊ณผ๋ผ๊ณ  ๋œจ๋ฉด ๊ต‰์žฅํžˆ ๋จธ๋ฆฌ๊ฐ€ ์•„ํŒŒ์ง€์ฃ .

์˜ค๋Š˜์€ ๋ถ€๋ถ„ํ•ฉ, ๊ตฌ๊ฐ„ํ•ฉ ๋ฌธ์ œ์— ์ฃผ๋กœ ์‚ฌ์šฉ๋˜๋Š” ๋ˆ„์ ํ•ฉ(Prefix sum)์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.


โ” ๋ถ€๋ถ„ํ•ฉ, ๊ตฌ๊ฐ„ํ•ฉ (Partial Sum){(Partial\ Sum)}

๋จผ์ € ๊ฐ„๋‹จํ•˜๊ฒŒ ๋ถ€๋ถ„ํ•ฉ๊ณผ ๊ตฌ๊ฐ„ํ•ฉ์— ๋Œ€ํ•ด ์•Œ์•„๋ด…์‹œ๋‹ค.

  • ๋ถ€๋ถ„ํ•ฉ 0 ~ n: ์ˆ˜์—ด(๋ฐฐ์—ด)์˜ 00๋ฒˆ์งธ๋ถ€ํ„ฐ nโˆ’1n-1๋ฒˆ์งธ๊นŒ์ง€์˜ ํ•ฉ์ž…๋‹ˆ๋‹ค.

    • ์ˆ˜ํ•™์‹ : Sn=a1+a2+a3+โ€ฆ+anS_n = a_1 + a_2 + a_3 + \dotsc + a_n
    • ํ”„๋กœ๊ทธ๋ž˜๋ฐ์‹ : S(n) = a[0] + a[1] + a[2] + ... + a[n-1]
  • ๊ตฌ๊ฐ„ํ•ฉ a ~ b : ์ˆ˜์—ด(๋ฐฐ์—ด)์˜ aa๋ฒˆ์งธ๋ถ€ํ„ฐ bb๋ฒˆ์งธ๊นŒ์ง€์˜ ํ•ฉ์ž…๋‹ˆ๋‹ค.

    • ์ˆ˜ํ•™์‹ : S(a,b)=aa+aa+1+โ€ฆ++ห™abโˆ’2+abโˆ’1+abS_{(a,b)} = a_a + a_{a+1} + \dotsc + \dot + a_{b-2} + a_{b-1} + a_b
    • ํ”„๋กœ๊ทธ๋ž˜๋ฐ์‹ : S(a, b) = a[a] + a[a+1] + ... + a[b-1] + a[b]

โ” ๋ˆ„์ ํ•ฉ (Prefix Sum)(Prefix\ Sum)

arrayarray 11 22 33 44 55 66 77 88 99 ......
prefix sumprefix\ sum 11 33 66 1010 1515 2121 2828 3636 4545 ......

์ž์—ฐ์ˆ˜๊ฐ€ ๋‚˜์—ด๋œ 1์ฐจ์› ์ˆ˜์—ด (array)(array)์ด ์žˆ์„ ๋•Œ
์ด ์ˆ˜์—ด์— ๋Œ€ํ•œ ๋ˆ„์ ํ•ฉ (prefix sum)(prefix\ sum)

๋ˆ„์ ํ•ฉ์€ ๋‚˜์—ด๋œ ์ˆ˜(์ˆ˜์—ด)์˜ ๋ˆ„์ ๋œ ํ•ฉ ์ž์ฒด ํ˜น์€ ๊ทธ๊ฒƒ์„ ๋‹ด์€ ์ˆ˜์—ด์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ๋˜ํ•œ, ๋ˆ„์ ํ•ฉ์˜ ๊ฐ ์š”์†Œ๋Š” ์ˆ˜์—ด์˜ nn๋ฒˆ์งธ๊นŒ์ง€ ์š”์†Œ์˜ ํ•ฉ์ด๊ธฐ ๋•Œ๋ฌธ์— ์ˆ˜์—ด์˜ ๋ถ€๋ถ„ํ•ฉ์ด๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ž ๊ทธ๋Ÿผ ๋ˆ„์ ํ•ฉ์€ ์–ด๋–ค ๊ฒฝ์šฐ์— ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ ๋งŒ๋“ค์–ด์ง„ ๊ฑธ๊นŒ์š”? ๋ˆ„์ ํ•ฉ ๋ฐฉ์‹์€ ์•„๋ž˜ ์œ ํ˜•์˜ ๋ฌธ์ œ ํ•ด๊ฒฐ์— ์ฃผ๋กœ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.

  • ๊ตฌ๊ฐ„ํ•ฉ / ๋ถ€๋ถ„ํ•ฉ (Partial Sum){(Partial\ Sum)}
  • ์นด์šดํŒ… ์ •๋ ฌ (CountingSort)(Counting Sort)

์ด์ œ 1์ฐจ์› ์ˆ˜์—ด๊ณผ 2์ฐจ์› ์ˆ˜์—ด๋กœ ๋‚˜๋ˆ„์–ด ์˜ˆ์‹œ๋ฅผ ๋ณด๋ฉฐ ์–ด๋–ป๊ฒŒ ๋งŒ๋“ค๊ณ  ์‚ฌ์šฉํ•˜๋Š”์ง€ ๋ฐฐ์›Œ๋ด…์‹œ๋‹ค.


๐Ÿงช 1์ฐจ์› ๋ฐฐ์—ด์—์„œ์˜ ๋ˆ„์ ํ•ฉ

1์ฐจ์› ๋ฐฐ์—ด์˜ ๋ˆ„์ ํ•ฉ์„ ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ•์€ ์•„์ฃผ ๊ฐ„๋‹จํ•ฉ๋‹ˆ๋‹ค.

  1. ๊ฐ™์€ ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์„ ๋งŒ๋“ญ๋‹ˆ๋‹ค.
  2. ํ•ด๋‹น ์ธ๋ฑ์Šค๊นŒ์ง€์˜ ์ดํ•ฉ์„ ๋‹ด์Šต๋‹ˆ๋‹ค.

์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ์—์„  ์•„๋ž˜์™€ ๊ฐ™์ด ์ž‘์„ฑํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

function prefixSums(arr) {
  const len = arr.length;
  const prefixSums = [];
  let sum = 0;

  for (let i = 0; i < len; ++i) {
    sum += arr[i];
    prefixSums[i] = sum;
  }

  return prefixSums;
}

๋งŒ์•ฝ sum๋ณ€์ˆ˜๋ฅผ ๋งŒ๋“ค์ง€ ์•Š๊ณ  ์‹ถ๋‹ค๋ฉด ์•„๋ž˜์™€ ๊ฐ™์ด ์ž‘์„ฑํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

function prefixSums(arr) {
  const len = arr.length;
  const prefixSums = [arr[0]];

  for (let i = 1; i < len; ++i) {
    prefixSums[i] = prefixSums[i - 1] + arr[i];
  }

  return prefixSums;
}

๐Ÿฅ‡ ๋ฌธ์ œ ํ’€์ด์— ์‚ฌ์šฉํ•ด๋ณด๊ธฐ

๋ฐฑ์ค€์˜ ๋Œ€ํ‘œ์ ์ธ ๊ตฌ๊ฐ„ํ•ฉ ๋ฌธ์ œ์ธ ๋ฐฑ์ค€ 11659 : ๊ตฌ๊ฐ„ ํ•ฉ ๊ตฌํ•˜๊ธฐ 4์ž…๋‹ˆ๋‹ค.

๋ฌธ์ œ

์ˆ˜ N๊ฐœ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, i๋ฒˆ์งธ ์ˆ˜๋ถ€ํ„ฐ j๋ฒˆ์งธ ์ˆ˜๊นŒ์ง€ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N๊ณผ ํ•ฉ์„ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ํšŸ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ˆ˜๋Š” 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์…‹์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์—๋Š” ํ•ฉ์„ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ๊ตฌ๊ฐ„ i์™€ j๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

์ด M๊ฐœ์˜ ์ค„์— ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ i๋ฒˆ์งธ ์ˆ˜๋ถ€ํ„ฐ j๋ฒˆ์งธ ์ˆ˜๊นŒ์ง€ ํ•ฉ์„ ์ถœ๋ ฅํ•œ๋‹ค.

์ œํ•œ

  • 1 โ‰ค N โ‰ค 100,000
  • 1 โ‰ค M โ‰ค 100,000
  • 1 โ‰ค i โ‰ค j โ‰ค N
์˜ˆ์ œ ์ž…๋ ฅ

5 3
5 4 3 2 1
1 3
2 4
5 5
์˜ˆ์ œ ์ถœ๋ ฅ

12
9
1

๐Ÿš€ ๋ˆ„์ ํ•ฉ์˜ ๋ชฉ์ 

์ž ๊ทธ๋Ÿผ ๋ˆ„์ ํ•ฉ์€ ์–ด๋–ค ๊ฒฝ์šฐ์— ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ ๋งŒ๋“ค์–ด์ง„ ๊ฑธ๊นŒ์š”? ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ์˜ˆ์‹œ๋กœ ๋“ค๋ฉด ์•„๋ž˜ ์œ ํ˜•์˜ ๋ฌธ์ œ์— ์ฃผ๋กœ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.

  • ๊ตฌ๊ฐ„ํ•ฉ / ๋ถ€๋ถ„ํ•ฉ (Partial Sum){(Partial\ Sum)}
  • ์นด์šดํŒ… ์ •๋ ฌ (CountingSort)(Counting Sort)

๋ฐฑ์ค€์˜ ๋Œ€ํ‘œ์ ์ธ ๊ตฌ๊ฐ„ํ•ฉ ๋ฌธ์ œ์ธ ๋ฐฑ์ค€ 11659 : ๊ตฌ๊ฐ„ ํ•ฉ ๊ตฌํ•˜๊ธฐ 4๋ฅผ ์˜ˆ์‹œ๋กœ ํ’€์–ด๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.


์ฐธ๊ณ  ๋ฌธํ—Œ