๐๏ธ ์๋ฃ๊ตฌ์กฐ์ ์๊ณ ๋ฆฌ์ฆ/์๊ณ ๋ฆฌ์ฆ,์๋ฃ๊ตฌ์กฐ15 ์ด์ 1 2 3 ๋ค์ [๊ทธ๋ํ] ์์ ์ ๋ ฌ, ์ต๋จ ๊ฒฝ๋ก ์์ ์ ๋ ฌ ๋ชจ๋ ๊ฐ์ ์ ๋ํด ์ฑ์ง์ ๋ง์กฑํ๋ ์์๋ก ์์ ์ ์ ๋ ฌํ๋ ๊ฒ ์์ ์ ๋ ฌ์ ์ธ์ดํด์ด ์๋ ๋ฐฉํฅ ๊ทธ๋ํ G=(V,E) ์์ V์ ๋ชจ๋ ์ ๋ค์ ์ ๋ ฌํ๋, '๊ฐ์ (i->j)๊ฐ ์กด์ฌํ๋ฉด ์ ๋ ฌ ๊ฒฐ๊ณผ์์ ์ ์ i๋ ์ ์ j ๋ณด๋ค ์์ ์์นํ๋ค.' ๋ผ๋ ์ฑ์ง์ ๋ง์กฑํด์ผํจ ์์ ์ ๋ ฌ์ ์ค์ผ์ค๋ง์ด๋, ๊ฐ์ค์น๋ฅผ ๊ฐ๊ณ ์ธ์ดํด์ด ์๋ ๋ฐฉํฅ ๊ทธ๋ํ์ ์ต๋จ ๊ฒฝ๋ก ์ฐพ๊ธฐ์๋ ์ฐ์ ์ปดํ์ผ๋ฌ์์ ์์ ์ ์์ฐจ์ ์ผ๋ก ์ฒ๋ฆฌํ๊ธฐ ์ํด์ ์ฌ์ฉ๋๊ธฐ๋ ํจ ์ต๋จ ๊ฒฝ๋ก ๋ชจ๋ ๊ฐ๋ฅํ ๊ฒฝ๋ก ์ค ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ ๋ชจ๋ ๊ฐ์ ๊ฐ์ค์น๊ฐ ์์ ๊ฐ์ค์น์ธ ์ธ์ดํด ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ ์์ ๊ฐ์ค์น๋ฅผ ํ์ฉํ์ง๋ง, ๊ฐ์ค์น ํฉ์ด ์์ธ ์ธ์ดํด ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ํ๋์ ์์ ์ ์ ์ผ๋ก๋ถํฐ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ์ ์ด๋ฅด๋ ์ต.. 2023. 12. 8. [๊ทธ๋ํ] ์ต์ ์ ์ฅ ํธ๋ฆฌ (ํ๋ฆผ/ํฌ๋ฃจ์ค์นผ/์ ๋์จ ํ์ธ) ์ฐ๊ฒฐ ๊ทธ๋ํ ๊ฐ์ ์ ๋ฐฉํฅ์ด ์๋ ๊ทธ๋ํ์์ ๋ชจ๋ ์ ์ ๋ค ๊ฐ์ ๊ฐ์ ์ ๋ฐ๋ผ ์๋ก ๋ค๋ค๋ฅผ ์ ์๋ ๊ทธ๋ํ ๊ทธ๋ํ ์ด๋ก ์์ 'ํธ๋ฆฌ'๋ "์ธ์ดํด์ด ์๋ ์ฐ๊ฒฐ๋ ๊ทธ๋ํ"๋ก ์ ์๋จ ํธ๋ฆฌ ์ต์ํ์ ๊ฐ์ ์ ์ฌ์ฉํ๋ฉด์ ์ฐ๊ฒฐ๋ ๊ทธ๋ํ ์ ์ฅ ํธ๋ฆฌ ๋น์ฉ ๊ทธ๋ํ์ ๊ฐ์ ์ ๊ฐ์ค์น๊ฐ ์๋ค๋ฉด, ์ ์ฅ ํธ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๋ ๊ฐ์ ์ ๊ฐ์ค์น๋ฅผ ๋ค ๋ํ ๊ฒ ์ต์ ์ ์ฅ ํธ๋ฆฌ ๊ฐ์ค์น๊ฐ ์๋ ๋ฌดํฅ ๊ทธ๋ํ๋ก๋ถํฐ ๋ง๋ค ์ ์๋ ๋ชจ๋ ์ ์ฅ ํธ๋ฆฌ ์ค, ๋น์ฉ์ด ๊ฐ์ฅ ๋ฎ์ ํธ๋ฆฌ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ ํ๋์ ์ ์ ์งํฉ์ ์ ์ ํค์๋๊ฐ๋ ๋ฐฉ์ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ ์ฌ๋ฌ ์ ์ ์งํฉ์ผ๋ก ์์ํด์ ์งํฉ๋ค์ ํฉ์ณ๋๊ฐ๋ ๋ฐฉ์ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ์ฐพ๋๋ค๋ ๊ฒ์ ๊ถ๊ทน์ ์ผ๋ก |V|-1๊ฐ์ ๊ฐ์ ์ ์ฐพ๋ ๊ณผ์ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ์๋ฌด ๊ฐ์ ๋ ์๋ ์ํ์์ ๊ฐ์ ์ ํ๋์ฉ ๋ํ๋ ์์ ์ .. 2023. 12. 8. [๊ทธ๋ํ] ๋๋น์ฐ์ ํ์ BFS & ๊น์ด์ฐ์ ํ์ DFS ๋ชจ๋ ์ ์ ์ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ๋ฒ : ๋๋น์ฐ์ ํ์ BFS, ๊น์ด์ฐ์ ํ์ DFS ๋๋น์ฐ์ ํ์ BFS ๋จผ์ ๋ฃจํธ์ ์์์ ์ฐจ๋ก๋ก ๋ฐฉ๋ฌธํจ ๋ค์์ผ๋ก ๋ฃจํธ ์์์ ์์, ๋ฃจํธ์์ 2๊ฐ์ ๊ฐ์ ์ ๊ฑฐ์ณ์ ๋๋ฌํ ์ ์๋ ์ ์ ๋ฐฉ๋ฌธ ๋ฃจํธ๋ก๋ถํฐ 3๊ฐ์ ๊ฐ์ ์ ๊ฑฐ์ณ์ ๋๋ค๋๋ ์ ์ ๋ค 4๊ฐ, 5๊ฐ... ์์ผ๋ก ๋ฐฉ๋ฌธํจ ๊น์ด์ฐ์ ํ์ DFS ๋ฃจํธ ์์ ์ ์ ์ ํ๋ ๋ฐฉ๋ฌธํ ๋ค์, ์๋๋ก ๋ด๋ ค๊ฐ ์ ์๋ ๊ณณ๊น์ง ๋ด๋ ค๊ฐ ๋ ์ด์ ๋ด๋ ค๊ฐ ์๊ฐ ์์ผ๋ฉด ์๋ก ๋๋์์ค๋ค๊ฐ ๋ด๋ ค๊ฐ ๊ณณ์ด ์์ผ๋ฉด ์ฆ๊ฐ ๋ด๋ ค๊ฐ BFS๋ ์์ผ๋ก ์ญ ํ์ด ๋๊ฐ๊ณ , DFS๋ ์๋๋ก(๊น์ด) ๊ฐ ์ ์๋ ๋ฐ๊น์ง ๊ฐ๋ค๊ฐ ๋งํ๋ฉด ๋๋์์์ ๋ค์ ๋ด๋ ค๊ฐ DFS์ ๊ธฐ๋ฐํ ํ์ ๋ฐฉ๋ฒ์ ๋ฐฑํธ๋ํน ์ด๋ผ๊ณ ๋ถ๋ฅด๊ธฐ๋ ํจ BFS ์ํ ์์ ์์ ์ ์ ์ผ๋ก ์ ํด์ง ์ ์ ์ ๋ฐฉ๋ฌธ(1๋ก ํ์) ์ ์ 1์ .. 2023. 12. 8. [๊ทธ๋ํ] ๊ทธ๋ํ ํํ๋ฐฉ๋ฒ ๊ทธ๋ํ ํ์์ด๋ ์ฌ๋ฌผ์ ์ ์ ๊ณผ ๊ฐ์ ์ผ๋ก ํํํ ๊ฒ ์ ์ ๋์์ด๋ ๊ฐ์ฒด๋ฅผ ๋ํ๋ ๊ฐ์ ์ ์ ๊ฐ์ ๊ด๊ณ๋ฅผ ๋ํ๋ ๊ฐ์ค์น๋ฅผ ์ฃผ์ด ์ ๋๋ฅผ ํํํ ์ ์์ ๊ทธ๋ํ์ ํํ ์ ํต์ ์ธ ๊ทธ๋ํ ํํ๋ฒ์๋ ํ๋ ฌ์ ์ด์ฉํ๋ ๋ฐฉ๋ฒ๊ณผ ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํ๋ ๋ฐฉ๋ฒ์ด ์์ ์ธ์ ํ๋ ฌ ํ๋ ฌ ํํ๋ฒ์ ์ดํดํ๊ธฐ ์ฝ๊ณ ๊ฐ์ ์ ์กด์ฌ ์ฌ๋ถ๋ฅผ ์ฆ๊ฐ ์ ์ ์์ n*n ํ๋ ฌ์ด ํ์ํ๋ฏ๋ก n^2์ ๋น๋กํ๋ ๊ณต๊ฐ์ด ํ์ํ๊ณ , ํ๋ ฌ ์ค๋น ๊ณผ์ ์์ ํ๋ ฌ์ ๋ชจ๋ ์์๋ฅผ ์ฑ์ฐ๋ ๋ฐ๋ง n^2์ ๋น๋กํ๋ ์๊ฐ์ด ๋ ๋ค ํํ๋ฐฉ๋ฒ ์ ์ i ์ ์ ์ j ์ฌ์ด์ ๊ฐ์ ์ด ์์ผ๋ฉด ํ๋ ฌ (i,j) (j,i) ์์์ ๊ฐ์ 1๋ก ํ ๋นํจ ๋ฐฉํฅ์ด ์๋ ๊ฒฝ์ฐ i->j ๋ฅผ (i,j)๋ก ํํ ๊ฐ์ค์น๊ฐ ์๋ ๊ฒฝ์ฐ ์์์ ๊ฐ์ ํ ๋นํจ ๋๋จธ์ง ์๋ฆฌ์๋ 0์ ํ ๋นํจ ์ธ์ ๋ฆฌ์คํธ ๊ฐ ์ ์ ์ ์ธ์ ํ ์ .. 2023. 12. 8. [ํด์ ํ ์ด๋ธ] ์ถฉ๋ ํด๊ฒฐ ์ถฉ๋ ์ด๋ค ํค๊ฐ ์ด๋ฏธ ์๋ฆฌ์ก๊ณ ์๋ ์ํ์์ ๋ค๋ฅธ ํค๊ฐ ์ฝ์ ์ ์๋ํ๋ ๊ฒ ๋์ผํ ์ฃผ์์ 2๊ฐ ์ด์์ ํค๊ฐ ํด์ฑ๋๋ ์ํฉ ์ถฉ๋ ํด๊ฒฐ ๋ฐฉ๋ฒ ์ฒด์ด๋ ๊ฐ๋ฐฉ ์ฃผ์ ๋ฐฉ๋ฒ ์ฒด์ด๋ ๊ฐ์ ์ฃผ์๋ก ํด์ฑ๋๋ ํค๋ฅผ ๋ชจ๋ ํ๋์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๋งค๋ฌ์์ ๊ด๋ฆฌํจ ํด์ํ ์ด๋ธ์ ํฌ๊ธฐ๊ฐ m์ด๋ฉด ์ต๋ m๊ฐ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๊ฐ ์กด์ฌํ ์ ์์ ๊ฐ์ ์ฃผ์๋ก ๋ค์ด์จ ํค๋ค์ ํด๋น ํค๋ ๋ค์์ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ก ๋งค๋ฌ๋ ค ์์ ์ฒด์ด๋์ ์์์ ํค๋ฅผ ์ฝ์ ํ ๋ ํด์๊ฐ์ด ๊ฐ๋ฆฌํค๋ ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ์ฝ์ ํจ ๋ฆฌ์คํธ์ ๋งจ ์์ ์ฝ์ ํ๋ ๊ฒ์ด ์ข์ ํค๋ฅผ ๊ฒ์ํ ๋ ํด๋น ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ํค๋ค์ ์ฐจ๋ก๋ก ์ง๋๊ฐ๋ฉด์ ์ฐพ์ ์ ์ฌ์จ์ด 1์ ๋์ด๋ ์ฌ์ฉํ ์์์ ๊ฐ๋ฐฉ ์ฃผ์ ๋ฐฉ๋ฒ ์ฒด์ด๋๊ณผ ๋ฌ๋ฆฌ ์ถ๊ฐ ๊ณต๊ฐ์ ์ฌ์ฉํ์ง ์์. ์ถฉ๋์ด ์ผ์ด๋๋๋ผ๋ ์ด๋ป๊ฒ๋ ์ฃผ์ด์ง ํ ์ด๋ธ ๊ณต๊ฐ์์ ํด๊ฒฐํจ ๋ชจ๋ ํค.. 2023. 12. 8. [ํด์ ํ ์ด๋ธ] ํด์ ํ ์ด๋ธ, ํด์ ํจ์ ํด์ ํ ์ด๋ธ์ ์๋ฃ๋ฅผ ๊ฒ์, ์ฝ์ , ์ญ์ ํ๋ ๋ฐ ํ๊ท ์๊ฐ์ด ๊ฐ๋ฅํ๊ฒ ํ์ฌ ๊ทน๋จ์ ํจ์จ์ ๋ค๋ค๋ฅธ ์๋ฃ๊ตฌ์กฐ ํค ์์ ์ ๊ฐ์ ๋ฐ๋ผ ์๋ฆฌ๊ฐ ๊ฒฐ์ ๋จ ํด์ ํ ์ด๋ธ์ ํค๊ฐ ์ ์ฅ๋ ์๋ฆฌ๋ฅผ ํค์ '๊ฐ'์ผ๋ก ๊ฒฐ์ ํ๋ ์๋ฃ๊ตฌ์กฐ ํด์ ํจ์๋ ์์์ ํท๊ฐ์ ์ ๋ ฅ์ผ๋ก ๋ฐ์ ์ฃผ์ ์ค ํ ๊ฐ์ ๋ฆฌํดํจ(๋ฆฌํด๊ฐ=ํด๋น ํค๋ฅผ ์ ์ฅํ๋ ์๋ฆฌ) ํด์ ํจ์ ๋๋๊ธฐ์ ๋ฐฉ๋ฒ ๊ณฑํ๊ธฐ ๋ฐฉ๋ฒ ์ถฉ๋ ์ด๋ค ํค๊ฐ ์ด๋ฏธ ์๋ฆฌ ์ก๊ณ ์๋ ์ํ์์ ๋ค๋ฅธ ํค๊ฐ ์ฝ์ ์ ์๋ํ๋ ๊ฒ ๋์ผํ ์ฃผ์์ 2๊ฐ ์ด์์ ํค๊ฐ ํด์ฑ๋๋ ์ํฉ ์ถฉ๋ ํด๊ฒฐ๋ฐฉ๋ฒ ์ฒด์ด๋ : ์ถฉ๋์ ์ผ์ผํจ ํค๋ค์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก ๊ด๋ฆฌํ๋ ๋ฐฉ๋ฒ ๊ฐ๋ฐฉ ์ฃผ์ ๋ฐฉ๋ฒ : ์ถฉ๋์ด ์ผ์ด๋๋๋ผ๋ ์ด๋ป๊ฒ๋ ์ฃผ์ด์ง ํ ์ด๋ธ ๊ณต๊ฐ์์ ํด๊ฒฐํ๋ ๊ฒ ๊ฒ์ ์๊ฐ ์ฒด์ด๋, ๊ฐ๋ฐฉ ์ฃผ์ ๋ฐฉ๋ฒ์ผ๋ก ๊ฒ์ํ ๋์ ๊ธฐ๋์๊ฐ ์ ์ฌ์จ ํด์ ํ ์ด๋ธ์ ์.. 2023. 11. 30. [ํธ๋ฆฌ] ๊ท ํ ๊ฒ์ ํธ๋ฆฌ (AVLํธ๋ฆฌ, ๋ ๋-๋ธ๋ํธ๋ฆฌ, B-ํธ๋ฆฌ) ๊ท ํ ์ด์ง ๊ฒ์ ํธ๋ฆฌ ์ต์ ์ ๊ฒฝ์ฐ์๋ ์ด์ง ํธ๋ฆฌ์ ๊ท ํ์ด ์ ๋ง๋๋ก ์ ์งํด์ ์์ ๋ค์ด ํญ์ O(logn)์๊ฐ์ ๋ณด์ฅํจ AVL ํธ๋ฆฌ ์๊ฐ ๊ท ํ, ๋์ด ๊ท ํ ์ด๋ค ๋ ธ๋๋ ์ข์๋ธ ํธ๋ฆฌ์ ์ฐ์๋ธ ํธ๋ฆฌ์ ๋์ด ์ฐจ๊ฐ 1๋ณด๋ค ํฌ์ง ์์ ์ํ๋ก ์ ์ง๋๋ ์ด์ง ๊ฒ์ ํธ๋ฆฌ ํ์ ์ฐ์ฐ ๊ท ํ์ด ๊นจ์ง ์๋ธ ํธ๋ฆฌ ์ค ๊ฐ์ฅ ๋ฎ์ ๊ณณ์ ์๋ ๊ฒ๋ถํฐ ์์ ์ ์์ํจ ๋จ์ผํ์ , ์ด์คํ์ AVLํธ๋ฆฌ ์ด์ ์ฝ์ ๊ณผ ์ญ์ ์๋ก์ด ๋ ธ๋๋ฅผ ์ฝ์ ํ๊ฑฐ๋ ๋ ธ๋๋ฅผ ์ญ์ ํ ๋, AVL ํธ๋ฆฌ๋ ๋ถ๊ท ํ๋๋ฅผ ์ฒดํฌํ๊ณ ํ์์ ๋ฐ๋ผ ํ์ ์ ์ํํ์ฌ ๊ท ํ์ ์ฌ์กฐ์ ๋ถ๊ท ํ๋ ์ฒดํฌ ๊ฐ ๋ ธ๋๋ ์์ ์ ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ์์ ํธ๋ฆฌ์ ๋์ด๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ๋ถ๊ท ํ๋๋ฅผ ๊ณ์ฐ. ๋ถ๊ท ํ๋๊ฐ 1์ ์ด๊ณผํ๋ฉด ๊ท ํ์ด ๊นจ์ง ๊ฒ์ผ๋ก ๊ฐ์ฃผ ํ์ ์ ํ ๊ท ํ์ด ๊นจ์ง ๊ฒฝ์ฐ, LL, RR, LR, RL ๋ค ๊ฐ.. 2023. 11. 27. ์ด์ 1 2 3 ๋ค์