๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก์•Œ๊ณ ๋ฆฌ์ฆ˜ (2)

Soony's House

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ(Sliding Window)

์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ(Sliding Window)๊ณ ์ •๋œ ์‚ฌ์ด์ฆˆ์˜ ์œˆ๋„์šฐ(์ฐฝ)์ด ๋ฐฐ์—ด ์•ˆ์„ ์ด๋™ํ•˜๋ฉด์„œ ์œˆ๋„์šฐ ๋‚ด์— ๋‹ด์€ ๋ฐ์ดํ„ฐ๋ฅผ ์ด์šฉํ•ด ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜.์ฐจ์ด๊ฐ€ ๋‚˜๋Š” ์–‘์ชฝ ๋ ์›์†Œ๋ฅผ ๊ฐฑ์‹ ํ•œ๋‹ค.์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐ๋Š” ํ•ญ์ƒ ๊ตฌ๊ฐ„์˜ ๋„ˆ๋น„๊ฐ€ ๊ณ ์ •๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. ๋งŒ์•ฝ, ์œˆ๋„์šฐ์˜ ํฌ๊ธฐ๊ฐ€ 3์ผ ๊ฒฝ์šฐ sw[0] = arr[0] + arr[1] + arr[2]...sw[n] = sw[n-1] - arr[n-1] + arr[n-1+(์œˆ๋„์šฐํฌ๊ธฐ)] ์˜ˆ์ œ Q. ์—ฐ์†๋œ index n๊ฐœ์˜ ํ•ฉ์˜ ์ตœ์†Œ๋ฅผ ๊ตฌํ•˜์‹œ์˜ค. ๊ทธ๋ฆฌ๊ณ  ํ•ฉ์ด ์ตœ์†Œ์ผ ๋•Œ์˜ ์ธ๋ฑ์Šค(a,b)๋ฅผ ๊ตฌํ•˜์‹œ์˜ค.(a 1. sw๋ฐฐ์—ด์— ๋ชจ๋‘ ๋‹ด๊ณ  ์ตœ์†Œ๊ฐ’ ๊ตฌํ•˜๋Š” ๋ฐฉ์‹import java.util.Scanner;public class Main { static Scanner sc..

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๋ˆ„์ ํ•ฉ(Prefix Sum) +Java๊ฐ์ฒด ๋ฐฐ์—ด ์„ ์–ธ & ์ƒ์„ฑ

๋ˆ„์ ํ•ฉ (Prefix Sum) ๋ˆ„์ ํ•ฉ์ด๋ž€? ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๊ฐ€ ์ฆ๊ฐ€ํ•จ์— ๋”ฐ๋ผ ๊ทธ ๋ˆ„์ ๋œ ํ•ฉ์„ ๋ฏธ๋ฆฌ ๊ตฌํ•ด ๋†“๋Š” ๊ฒƒ, '์ „์ฒ˜๋ฆฌ' ๋ผ๊ณ ๋„ ํ•จ.arr๋ฐฐ์—ด์„ ์ผ์ผํžˆ for๋ฌธ์œผ๋กœ ๋Œ๋ฉด์„œ ํ•ฉ์„ ๊ตฌํ•˜๋ฉด ๋˜๋Š”๊ฒƒ ์•„๋‹Œ๊ฐ€๋ž€ ์˜๋ฌธ์„ ๋˜์งˆ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ์‹œ๊ฐ„๋ณต์žก๋„ ์ธก๋ฉด์—์„œ ์„ฑ๋Šฅ์ด ์ €ํ•˜๋œ๋‹ค. (ํ…Œ์ŠคํŠธ์ผ€์ด์Šค์—์„œ ์‹œ๊ฐ„์ดˆ๊ณผ ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ•˜๊ธฐ๋„ ํ•จ..) ๊ทธ๋Ÿฌ๋ฏ€๋กœ ๋ˆ„์ ํ•ฉ์„ ๋ฏธ๋ฆฌ ๊ตฌํ•˜์—ฌ ์‚ฌ์šฉํ•œ๋‹ค. ๋ˆ„์ ํ•ฉ ๊ตฌํ˜„ํฌ๊ธฐ๊ฐ€ 10์ธ arr ๋ฐฐ์—ด์˜ ๋ˆ„์ ํ•ฉ์„ ๊ตฌํ•ด๋ณด์ž 1. ๋ˆ„์ ํ•ฉ์œผ๋กœ [a] ~ [b] ์˜ ํ•ฉ์„ ๊ตฌํ•˜๊ธฐ. " acc [ b ] - acc [ a - 1 ] " 2. acc๋ฐฐ์—ด์„ ์ฑ„์šฐ๊ธฐ์ธ๋ฑ์Šค 0 ์ผ๋•Œ๋Š” arr[0] ๊ทธ ์ž์ฒด๊ฐ€ ๋œ๋‹ค.๊ทธ ์ดํ›„๋ถ€ํ„ฐ๋Š” acc[i] = acc[i-1] + arr[i] " acc[0]=..