์ ์ฒด ๊ธ
-
[2019 ๋๊ณ ๋ชจ๊ฐ์ฝ] 6์ฐจ์ - ์์๋ชจ์ฌ์ ๊ฐ์ ์ฝ๋ฉ/2019 ๋๊ณ ๋ชจ๊ฐ์ฝ 2022. 3. 13. 00:08
ํด์ํ ์ด๋ธ ํด์ํ ์ด๋ธ์ด ๋ฌด์์ธ์ง ์๊ณ ๊ฐ๊ฐ ์กฐ์ฌ๋ฐฉ๋ฒ๋ค์ ๋ํด ์ดํดํ๊ณ ๋๋ค ์กฐ์ฌ๋ฐฉ๋ฒ์ ํด๋นํ๋ ์ฝ๋๋ฅผ ์์ฑํด๋ณธ๋ค. - ์์ฐจ์กฐ์ฌ, ์ฌํด์ฑ, ์ ๊ณฑ์กฐ์ฌ, ์ด์คํด์ฑ
-
[2019 ๋๊ณ ๋ชจ๊ฐ์ฝ] 5์ฐจ์ - ๊ฒฐ๊ณผ๋ชจ์ฌ์ ๊ฐ์ ์ฝ๋ฉ/2019 ๋๊ณ ๋ชจ๊ฐ์ฝ 2022. 3. 13. 00:08
์์ ์ด์งํธ๋ฆฌ์ ํํ ์๊ณ ๋ฆฌ์ฆ 1. ์์ ์ด์งํธ๋ฆฌ ์ดํด ์์ ์ด์งํธ๋ฆฌ๋ ์ด์งํธ๋ฆฌ์์ ๋ฆฌํ๊ฐ ์ผ์ชฝ๋ถํฐ ์์๋๋ก ์ฑ์์ง๋ ๊ฒ์ด๋ค. ๋ถ๋ชจ์ ์ธ๋ฑ์ค๊ฐ i ๋ผ๋ฉด ์์์ ์ธ๋ฑ์ค๋ 2i+1, 2i+2๊ฐ ๋๋ค. โ 2. ํํ ์๊ณ ๋ฆฌ์ฆ ์์ ์ด์งํธ๋ฆฌ์์ ๋ฆฌํ-๋ฃจํธ๋ก ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์ค๋ฆ์ฐจ์ ๋๋ ๋ด๋ฆผ์ฐจ์์ผ๋ก ๋์ด์๋ ๊ฒ์ด๋ค. ๋งฅ์คํํ : ์ค๋ฆ์ฐจ์์ผ๋ก ๋์ด์๋ ์์ ์ด์งํธ๋ฆฌ ํํํ : ํํ ํน์ฑ์ ๋ง์กฑํ๋๋ก ์์๋ค์ ์ฌ๋ฐฐ์ด โ 1) ํํํ๋ฉ์๋ - Max_heapify() : ๋ถ๋ชจ์ ์์๊ฐ์ ํฌ๊ธฐ๋ฅผ ๋น๊ตํ์ฌ ์์๋ฅผ ๋ฐฐ์ดํ๊ณ ์ฌ๊ท๋ฅผ ํตํด ๋ถ๋ชจ์์ ๋ฆฌํ๊น์ง ์ฌ๋ฐฐ์ดํ๋ค. โ 2) ์ฝ์ ๋ฉ์๋ - push(), pushSort() : ํธ๋ฆฌ์ ๋งจ๋ง์ง๋ง์ ์ฝ์ ํ๊ณ ๋ถ๋ชจ์ ๋น๊ตํ๋ฉฐ ๋ฆฌํ-๋ฃจํธ๊ฒฝ๋ก๋ก ์์๋ฅผ ์ฌ๋ฐฐ์ดํ๋ค. push(int x) - ํฌ๋ฆฌ๋ฅผ..
-
[2019 ๋๊ณ ๋ชจ๊ฐ์ฝ] 5์ฐจ์ - ์์๋ชจ์ฌ์ ๊ฐ์ ์ฝ๋ฉ/2019 ๋๊ณ ๋ชจ๊ฐ์ฝ 2022. 3. 13. 00:06
์์ ์ด์งํธ๋ฆฌ์ ํํ ์๊ณ ๋ฆฌ์ฆ 1. ์์ ์ด์งํธ๋ฆฌ์ ๋ํด ์ดํดํ๊ธฐ 2. ์์ ์ด์งํธ๋ฆฌ๋ฅผ ์ด์ฉํ ํํ์ ๋ํด ์ดํดํ๊ธฐ - ํํํ ์๊ณ ๋ฆฌ์ฆ๊ณผ ํํ ๊ตฌ์ถ ์๊ณ ๋ฆฌ์ฆ ์ดํดํ๊ธฐ
-
[2019 ๋๊ณ ๋ชจ๊ฐ์ฝ] 4์ฐจ์ - ๊ฒฐ๊ณผ๋ชจ์ฌ์ ๊ฐ์ ์ฝ๋ฉ/2019 ๋๊ณ ๋ชจ๊ฐ์ฝ 2022. 3. 13. 00:06
์ด์งํธ๋ฆฌ ์ด์งํธ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ์ดํดํ๊ณ ๊ตฌํํ๋ ๊ฒ์ ๋ชฉํ๋ก ํจ ์ด์งํธ๋ฆฌ๋ฅผ ๊ตฌํํ๋ BinaryTreeํด๋์ค๋ฅผ ์์ฑํ๊ณ ์ด ํด๋์ค๋ ํธ๋ฆฌ ์ฝ์ ๋ฉ์๋, ํธ๋ฆฌ ํ์ ๋ฉ์๋, ํ์์ํ ๋ฉ์๋, ํธ๋ฆฌ ๊น์ด ๊ณ์ฐ ๋ฉ์๋๋ก ๊ตฌ์ฑ๋๋ค. โ 1) ํ๋ ๋ณ์์ ์์ฑ์ left์ right๋ key๋ฅผ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ, ์ค๋ฅธ์ชฝ์ผ๋ก์ ์ฐ๊ฒฐ์ ๋ํ๋ธ๋ค. โ 2) ์ฝ์ ๋ฉ์๋ : BinaryTreeํ์ ํฌ์ธํฐ๋ฅผ ๋ง๋ค์ด ์ฝ์ ํ ์๋ฆฌ์ ์ด๋ํด ์ฝ์ ํ๋ค. : key์ ๊ฐ๋ณด๋ค ์์ ์๋ ์ผ์ชฝ์ ํฐ์๋ ์ค๋ฅธ์ชฝ์ ์ฝ์ ํ๋ค. ํธ๋ฆฌ๋ key๊ฐ์ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ์ผ๋ก ๋๋์ด์ ธ ๊ฒฝ์ฐ๋ฅผ ๋๋๋๊ฒ ์ค์ํ ๊ฒ์ ๋๊ผ๋ค. โ 3) ํ์๋ฉ์๋ : ํ์ํ ๊ฐ์ key๊ฐ๊ณผ ๋น๊ตํ๋ฉฐ ํฌ์ธํฐ๋ฅผ ์ด๋์์ผ ์ฐพ๋๋ค. โ 4) ํ์์ํ ๋ฉ์๋ : ์ฌ๊ท๋ฅผ ์ด์ฉํ์ฌ ํธ๋ฆฌ๋ฅผ ..