๐Ÿ“‚ ์ž๋ฃŒ๊ตฌ์กฐ/ํŠธ๋ฆฌ

    ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ(Segment Tree)

    1. ๊ฐœ๋… ๐Ÿ›ซ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ(Segment Tree)๋ž€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ฐ์ดํ„ฐ๊ฐ€ ์กด์žฌํ•  ๋•Œ ํŠน์ • ๊ตฌ๊ฐ„์˜ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ๋ฐ ์‚ฌ์šฉํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ํŠธ๋ฆฌ ์ข…๋ฅ˜ ์ค‘ ํ•˜๋‚˜๋กœ ์ด์ง„ํŠธ๋ฆฌ์˜ ํ˜•ํƒœ์ด๋ฉฐ, ํŠน์ • ๊ตฌ๊ฐ„์˜ ํ•ฉ์„ ๊ฐ€์žฅ ๋น ๋ฅด๊ฒŒ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์žฅ์ ์ด ์žˆ๋‹ค. O(log N) 2. ๋™์ž‘๋ฐฉ์‹ ๐Ÿš ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋ฅผ ์ด์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ์šฐ์„  '๊ตฌ๊ฐ„ ํ•ฉ ํŠธ๋ฆฌ'๋ฅผ ์ƒ์„ฑํ•ด์•ผ ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  '๊ตฌ๊ฐ„ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ํ•จ์ˆ˜'์™€ '์›์†Œ๋ฅผ ์ˆ˜์ •ํ•˜๋Š” ํ•จ์ˆ˜'๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ตฌ๊ฐ„ ํ•ฉ์„ ๊ตฌํ•˜๊ณ  ํŠน์ • ์›์†Œ๋ฅผ ์ˆ˜์ •ํ•  ์ˆ˜ ์žˆ๋‹ค. '1 9 3 8 4 5 5 9 10 3 4 5'๋ผ๋Š” 12๊ฐœ์˜ ์›์†Œ๋ฅผ ๊ฐ€์ง„ ๋ฐฐ์—ด์ด ์ฃผ์–ด์กŒ์„ ๋•Œ ์„ธ๊ทธ๋จผํŠธ ํŠธ๋ฆฌ๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ตฌ๊ฐ„ ํ•ฉ์„ ๊ตฌํ•ด๋ณด์ž. 1. ๊ตฌ๊ฐ„ ํ•ฉ ํŠธ๋ฆฌ ์ƒ์„ฑํ•˜๊ธฐ '๊ตฌ๊ฐ„'์€ ์›๋ž˜ ๋ฐ์ดํ„ฐ ๋ฒ”์œ„๋ฅผ ๋ฐ˜์”ฉ ๋ถ„ํ• ํ•˜๋Š” ๊ฒƒ์œผ๋กœ ์„ค์ •ํ•œ๋‹ค. ์ตœ์ƒ๋‹จ ๋…ธ๋“œ..

    [์ž๋ฃŒ๊ตฌ์กฐ] ํž™(Heap)

    1. ์ •์˜ ๐Ÿณ ํž™(Heap)์ด๋ž€ ์—ฌ๋Ÿฌ ๊ฐ’๋“ค ์ค‘ ์ตœ๋Œ“๊ฐ’ ํ˜น์€ ์ตœ์†Ÿ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ์•„๋‚ด๊ธฐ ์œ„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ํž™์˜ ํŠน์ง• ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ์˜ ์ผ์ข…์ด๋‹ค. ๋ฐ˜์ •๋ ฌ ์ƒํƒœ์ด๋‹ค. ์ตœ๋Œ€ํž™(Max Heap) ๋˜๋Š” ์ตœ์†Œํž™(Min Heap)์— ๋”ฐ๋ผ์„œ ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ํ•ญ์ƒ ๊ฐ€์žฅ ํฐ ๊ฐ’์ด๊ฑฐ๋‚˜ ๊ฐ€์žฅ ์ž‘์€ ๊ฐ’์„ ์œ ์ง€ํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ์ค‘๋ณต๋œ ๊ฐ’์„ ํ—ˆ์šฉํ•œ๋‹ค. ํž™์˜ ์ข…๋ฅ˜ ์ตœ๋Œ€ ํž™ (Max Heap) ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’์ด ์ž์‹ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ ํ˜•์‹ ์ตœ์†Œ ํž™ (Min Heap) ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’์ด ์ž์‹ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ ํ˜•์‹ 2. ๋™์ž‘ ๋ฐฉ์‹ ๐ŸŸ ์ธ๋ฑ์Šค 0 1 2 3 4 5 6 7 8 ๊ฐ’ - 9 7 6 4 5 1 3 8 Heap์€ ๋ฐฐ์—ด์„ ํ†ตํ•ด ์‰ฝ๊ฒŒ ๊ตฌํ˜„์ด ๊ฐ€๋Šฅํ•˜๋‹ค. ๊ทธ ์ด์œ ๋Š” ํž™์ด ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ์ด..