๐ ์๋ฃ๊ตฌ์กฐ/ํธ๋ฆฌ

์ธ๊ทธ๋จผํธ ํธ๋ฆฌ(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์ ๋ฐฐ์ด์ ํตํด ์ฝ๊ฒ ๊ตฌํ์ด ๊ฐ๋ฅํ๋ค. ๊ทธ ์ด์ ๋ ํ์ด ์์ ์ด์งํธ๋ฆฌ์ด..