Just keep coding ...

์ž๋ฃŒ๊ตฌ์กฐ

2024. 10. 25. 08:39ใ†์ž๋ฃŒ๊ตฌ์กฐ

728x90

๐Ÿ‘‰๋‹ค์ˆ˜์˜ ์ž๋ฃŒ(Data)๋ฅผ ๋‹ด๊ธฐ ์œ„ํ•œ ๊ตฌ์กฐ

์ž๋ฃŒ๊ตฌ์กฐ์˜ ํ•„์š”์„ฑ์— ๋Œ€ํ•ด์„œ ์ดํ•ดํ•  ํ•„์š”๊ฐ€ ์žˆ๋‹ค

์„ฑ๋Šฅ๋น„๊ต: ์ž๋ฃŒ๊ตฌ์กฐ/์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ ์ธก์ • ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ์ดํ•ดํ•  ํ•„์š”๊ฐ€ ์žˆ๋‹ค.

์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ œ๋Œ€๋กœ ์ดํ•ดํ•˜์ง€ ๋ชปํ•˜๋ฉด ๋ถˆํ•„์š”ํ•˜๊ฒŒ ๋ฉ”๋ชจ๋ฆฌ์™€ ๊ณ„์‚ฐ์„ ๋‚ญ๋น„ํ•œ๋‹ค.

 

๐Ÿ‘‰์„ ํ˜• ๊ตฌ์กฐ

ํ•˜๋‚˜์˜ ๋ฐ์ดํ„ฐ ๋’ค์— ๋‹ค๋ฅธ ๋ฐ์ดํ„ฐ๊ฐ€ ํ•˜๋‚˜ ์กด์žฌํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ

๋ฐ์ดํ„ฐ๊ฐ€ ์ผ๋ ฌ๋กœ ์—ฐ์†์ ์œผ๋กœ(์ˆœ์ฐจ์ ์œผ๋กœ) ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค.

- ๋ฐฐ์—ด

- ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (linked list)

- ์Šคํƒ

- ํ, ๋ฑ(deque)

 

๐Ÿ‘‰๋น„์„ ํ˜• ๊ตฌ์กฐ

ํ•˜๋‚˜์˜ ๋ฐ์ดํ„ฐ ๋’ค์— ๋‹ค๋ฅธ ๋ฐ์ดํ„ฐ๊ฐ€ ์—ฌ๋Ÿฌ ๊ฐœ ์˜ฌ ์ˆ˜ ์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ

๋ฐ์ดํ„ฐ๊ฐ€ ์ผ์ง์„ ์ƒ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์ง€ ์•Š์•„๋„ ๋œ๋‹ค

- ํŠธ๋ฆฌ

- ๊ทธ๋ž˜ํ”„ (BFS, DFS ๋“ฑ)

 

๋ฌธ์ œ ์ƒํ™ฉ์— ๋งž๋Š” ์ ์ ˆํ•œ ์ž๋ฃŒ๊ตฌ์กฐ๊ฐ€ ์‚ฌ์šฉ๋˜์–ด์•ผ ํ•œ๋‹ค.

 

์‹œ๊ฐ„ ๋ณต์žก๋„

- ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์‚ฌ์šฉ๋˜๋Š” ์—ฐ์ƒ ํšŸ์ˆ˜๋ฅผ ์ธก์ •ํ•œ๋‹ค.

๊ณต๊ฐ„ ๋ณต์žก๋„

- ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์‚ฌ์šฉ๋˜๋Š” ๋ฉ”๋ชจ๋ฆฌ์˜ ์–‘์„ ์ธก์ •ํ•œ๋‹ค.

๊ณต๊ฐ„์„ ๋งŽ์ด ์‚ฌ์šฉํ•˜๋Š” ๋Œ€์‹  ์‹œ๊ฐ„์„ ๋‹จ์ถ•ํ•˜๋Š” ๋ฐฉ๋ฒ•์ด ํ”ํžˆ ์‚ฌ์šฉ๋œ๋‹ค.

 

๐Ÿ‘‰ํ”„๋กœ๊ทธ๋žจ์˜ ์„ฑ๋Šฅ ์ธก์ • ๋ฐฉ๋ฒ•: Big-O ํ‘œ๊ธฐ๋ฒ•

- ํŠน์ •ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์–ผ๋งˆ๋‚˜ ํšจ์œจ์ ์ธ์ง€ ์ˆ˜์น˜์ ์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

- ๊ฐ€์žฅ ๋น ๋ฅด๊ฒŒ ์ฆ๊ฐ€ํ•˜๋Š” ํ•ญ๋งŒ์„ ๊ณ ๋ คํ•˜๋Š” ํ‘œ๊ธฐ๋ฒ•

 

 

ํ˜„์‹ค์—์„œ๋Š” ๋™์ž‘ ์‹œ๊ฐ„์ด 1์ดˆ ์ด๋‚ด์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์„ค๊ณ„ํ•  ํ•„์š”๊ฐ€ ์žˆ๋‹ค.

Big-O ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ํ‘œ๊ธฐํ•  ๋–„๋Š” ๊ฐ€์žฅ ํฐ ํ•ญ๋งŒ์„ ํ‘œ์‹œํ•œ๋‹ค.

 

์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ ๋ฉ”๋ชจ๋ฆฌ์˜ ํฌ๊ธฐ๋ฅผ ๋‚˜ํƒ€๋‚ผ ๋–„๋Š” ์ผ๋ฐ˜์ ์œผ๋กœ MB๋‹จ์œ„๋กœ ํ‘œ๊ธฐํ•œ๋‹ค.

 

์ถœ์ฒ˜:  https://fastcampus.co.kr/dev_online_upjscodingtest ,https://en.wihipedia.org/wiki/Big_O_notation

 

728x90