๐งฎ ์๊ณ ๋ฆฌ์ฆ : ๋์ ํฉ (Prefix sum)
2023-02-04
! TIME LIMIT EXCEEDED !
์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํ๋ค๋ณด๋ฉด ๋จ์ํ ๋ฐ๋ณต ์ํํ๋ฉด ์๊ฐ ์ด๊ณผ์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ ํ์ ๋ฌธ์ ๊ฐ ๋ง์ด ๋ํ๋ฉ๋๋ค. ์๊ตฌํ๋ ๊ฒฐ๊ณผ๋ฅผ ์ฐพ๋ ๋ก์ง์ ์ด์ฌํ ๊ตฌํํ ๋ค์ โ์ค ๋๋์ด ๊ตฌํด์ง๋ค!โ ํ๊ณ ์ ์ถํ๋๋ฐ, ์๊ฐ ์ด๊ณผ
๋ผ๊ณ ๋จ๋ฉด ๊ต์ฅํ ๋จธ๋ฆฌ๊ฐ ์ํ์ง์ฃ .
์ค๋์ ๋ถ๋ถํฉ, ๊ตฌ๊ฐํฉ ๋ฌธ์ ์ ์ฃผ๋ก ์ฌ์ฉ๋๋ ๋์ ํฉ
(Prefix sum)์ ๋ํด ์์๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
โ ๋ถ๋ถํฉ, ๊ตฌ๊ฐํฉ
๋จผ์ ๊ฐ๋จํ๊ฒ ๋ถ๋ถํฉ๊ณผ ๊ตฌ๊ฐํฉ์ ๋ํด ์์๋ด ์๋ค.
๋ถ๋ถํฉ
0 ~ n
: ์์ด(๋ฐฐ์ด)์ ๋ฒ์งธ๋ถํฐ ๋ฒ์งธ๊น์ง์ ํฉ์ ๋๋ค.- ์ํ์ :
- ํ๋ก๊ทธ๋๋ฐ์ :
S(n) = a[0] + a[1] + a[2] + ... + a[n-1]
๊ตฌ๊ฐํฉ
a ~ b
: ์์ด(๋ฐฐ์ด)์ ๋ฒ์งธ๋ถํฐ ๋ฒ์งธ๊น์ง์ ํฉ์ ๋๋ค.- ์ํ์ :
- ํ๋ก๊ทธ๋๋ฐ์ :
S(a, b) = a[a] + a[a+1] + ... + a[b-1] + a[b]
โ ๋์ ํฉ
์์ฐ์๊ฐ ๋์ด๋ 1์ฐจ์ ์์ด ์ด ์์ ๋
์ด ์์ด์ ๋ํ ๋์ ํฉ
๋์ ํฉ์ ๋์ด๋ ์(์์ด)์ ๋์ ๋ ํฉ ์์ฒด ํน์ ๊ทธ๊ฒ์ ๋ด์ ์์ด์ ์๋ฏธํฉ๋๋ค. ๋ํ, ๋์ ํฉ์ ๊ฐ ์์๋ ์์ด์ ๋ฒ์งธ๊น์ง ์์์ ํฉ์ด๊ธฐ ๋๋ฌธ์ ์์ด์ ๋ถ๋ถํฉ์ด๋ผ๊ณ ํ ์ ์์ต๋๋ค.
์ ๊ทธ๋ผ ๋์ ํฉ์ ์ด๋ค ๊ฒฝ์ฐ์ ์ฌ์ฉํ๊ธฐ ์ํด์ ๋ง๋ค์ด์ง ๊ฑธ๊น์? ๋์ ํฉ ๋ฐฉ์์ ์๋ ์ ํ์ ๋ฌธ์ ํด๊ฒฐ์ ์ฃผ๋ก ์ฌ์ฉ๋ฉ๋๋ค.
- ๊ตฌ๊ฐํฉ / ๋ถ๋ถํฉ
- ์นด์ดํ ์ ๋ ฌ
์ด์ 1์ฐจ์ ์์ด๊ณผ 2์ฐจ์ ์์ด๋ก ๋๋์ด ์์๋ฅผ ๋ณด๋ฉฐ ์ด๋ป๊ฒ ๋ง๋ค๊ณ ์ฌ์ฉํ๋์ง ๋ฐฐ์๋ด ์๋ค.
๐งช 1์ฐจ์ ๋ฐฐ์ด์์์ ๋์ ํฉ
1์ฐจ์ ๋ฐฐ์ด์ ๋์ ํฉ์ ๋ง๋๋ ๋ฐฉ๋ฒ์ ์์ฃผ ๊ฐ๋จํฉ๋๋ค.
- ๊ฐ์ ํฌ๊ธฐ์ ๋ฐฐ์ด์ ๋ง๋ญ๋๋ค.
- ํด๋น ์ธ๋ฑ์ค๊น์ง์ ์ดํฉ์ ๋ด์ต๋๋ค.
์๋ฐ์คํฌ๋ฆฝํธ์์ ์๋์ ๊ฐ์ด ์์ฑํ ์ ์์ต๋๋ค.
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
๐ ๋์ ํฉ์ ๋ชฉ์
์ ๊ทธ๋ผ ๋์ ํฉ์ ์ด๋ค ๊ฒฝ์ฐ์ ์ฌ์ฉํ๊ธฐ ์ํด์ ๋ง๋ค์ด์ง ๊ฑธ๊น์? ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ์์๋ก ๋ค๋ฉด ์๋ ์ ํ์ ๋ฌธ์ ์ ์ฃผ๋ก ์ฌ์ฉ๋ฉ๋๋ค.
- ๊ตฌ๊ฐํฉ / ๋ถ๋ถํฉ
- ์นด์ดํ ์ ๋ ฌ
๋ฐฑ์ค์ ๋ํ์ ์ธ ๊ตฌ๊ฐํฉ ๋ฌธ์ ์ธ ๋ฐฑ์ค 11659 : ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 4
๋ฅผ ์์๋ก ํ์ด๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.