์๋ฃ๊ตฌ์กฐ6 ์ด์ 1 ๋ค์ [๊ทธ๋ํ] ์์ ์ ๋ ฌ, ์ต๋จ ๊ฒฝ๋ก ์์ ์ ๋ ฌ ๋ชจ๋ ๊ฐ์ ์ ๋ํด ์ฑ์ง์ ๋ง์กฑํ๋ ์์๋ก ์์ ์ ์ ๋ ฌํ๋ ๊ฒ ์์ ์ ๋ ฌ์ ์ธ์ดํด์ด ์๋ ๋ฐฉํฅ ๊ทธ๋ํ 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. [์คํ] ๋ฐฐ์ด ๊ธฐ๋ฐ ์คํ๊ณผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ๊ธฐ๋ฐ ์คํ Stack ์คํ์ ํ์ ์ ์ถ์ด๋ผ๋ ๊ท์น์ ๋ฐ๋ผ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๊ณ ์ ๊ทผํ๋ ์ ํ ์๋ฃ๊ตฌ์กฐ ์ฌ์ฉ ์์ : ์น ๋ธ๋ผ์ฐ์ ์ ๋ค๋ก ๊ฐ๊ธฐ ๊ธฐ๋ฅ, ๋ฌธ์์ด ์ญ์, ๊ดํธ ๊ฒ์ฌ, ์คํ ์ทจ์ ๊ธฐ๋ฅ, ์ฌ๊ท ํจ์ ํธ์ถ ์คํ์ ๊ฐ๋ ์คํ์ LIFO(Last In, First Out) ๋๋ FILO(First In, Last Out) ์์น์ ๋ฐ๋ผ ์๋ํ๋ ์๋ฃ๊ตฌ์กฐ ์ด ์์น์ ๊ฐ์ฅ ๋ง์ง๋ง์ ์ฝ์ ๋ ์์๊ฐ ๊ฐ์ฅ ๋จผ์ ์ ๊ฑฐ๋๋ค๋ ๊ฒ์ ์๋ฏธํจ ์คํ ์๋ฃ๊ตฌ์กฐ์ ADT(์ถ์ ๋ฐ์ดํฐ ํ์ ) Push : ์คํ์ ๋งจ ์์ ์์๋ฅผ ์ถ๊ฐํฉ๋๋ค. Pop : ์คํ์ ๋งจ ์์์ ์์๋ฅผ ์ ๊ฑฐํ๊ณ , ๊ทธ ์์๋ฅผ ๋ฐํํฉ๋๋ค. Peek : ์คํ์ ๋งจ ์ ์์๋ฅผ ๋ฐํํ์ง๋ง, ์ ๊ฑฐํ์ง ์์ต๋๋ค. IsEmpty : ์คํ์ด ๋น์ด ์๋์ง ํ์ธํฉ๋๋ค. ๋ฐฐ์ด ๊ธฐ๋ฐ ์คํ (Sta.. 2023. 11. 21. [๋ฆฌ์คํธ] ๋ฐฐ์ด ๋ฆฌ์คํธ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ํ ์ ๋ฆฌ์คํธ ์์ ์์ ๋ฆฌ์คํธ, ๋ธ๋ ๋ฆฌ์คํธ, ์๋น์ค๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ์ฌ๋ ๋ฆฌ์คํธ ๋ฆฌ์คํธ ์๋ฃ๊ตฌ์กฐ์ ADT(์ถ์ ๋ฐ์ดํฐ ํ์ ) ๋ฆฌ์คํธ์ ๊ธฐ๋ณธ ์ ์ ์ค ์ธ์์ ธ ์๋ ๋ฐ์ดํฐ ADT i๋ฒ์งธ ์๋ฆฌ์ ์์ x๋ฅผ ์ฝ์ ํ๋ค. i๋ฒ์งธ ์์๋ฅผ ์ญ์ ํ๋ค. ์์ x๋ฅผ ์ญ์ ํ๋ค. i๋ฒ์งธ ์์๋ฅผ ์๋ ค์ค๋ค. ์์ x๊ฐ ๋ช ๋ฒ์งธ ์์์ธ์ง ์๋ ค์ค๋ค. ๋ฆฌ์คํธ์ ์ฌ์ด์ฆ(์์์ ์ด ์)๋ฅผ ์๋ ค์ค๋ค. ํ์ด์ฝ๋ฅ ๋ฆฌ์คํธ๋ฅผ ๊ธฐ๋ณธ ์๋ฃ๊ตฌ์กฐ๋ก ์ ๊ณตํ๋ฉฐ, ์ ์์ ๋ณด๋ค ํจ์ฉ ๋ ๋ง์ ์์ ์ ์ง์ํจ ์๋ฐ๋ ์ธ์ด ์์ฒด์์ ๋ฆฌ์คํธ๋ฅผ java.util ํจํค์ง์์ ์ ๊ณตํจ ๋ฐฐ์ด ๋ฆฌ์คํธ ArrayList 1. ๊ตฌ์ฑ์์ ๋ด๋ถ๋ฐฐ์ด : ArrayList๋ ๋ด๋ถ์ ์ผ๋ก ๋ฐฐ์ด(Object[])์ ์ฌ์ฉํด ๋ฐ์ดํฐ๋ฅผ ์ ์ฅ. ์ด ๋ฐฐ์ด์ ํ์์ ๋ฐ๋ผ ๋์ ์ผ๋ก ํฌ๊ธฐ๊ฐ ์กฐ์ ๋จ. ์ฉ๋ : .. 2023. 11. 21. ์ด์ 1 ๋ค์