๐Ÿ‘ฉ๐Ÿปโ€๐Ÿ’ปTIL13. ์ž๋ฃŒ ๊ตฌ์กฐ (Data Structure)

Lilyยท2021๋…„ 6์›” 7์ผ
0

Today I Learned

๋ชฉ๋ก ๋ณด๊ธฐ
13/30
post-thumbnail

์ด ๊ธ€์€ Boostcourse ๋ชจ๋‘๋ฅผ ์œ„ํ•œ ์ปดํ“จํ„ฐ ๊ณผํ•™์„ ์ˆ˜๊ฐ•ํ•˜๊ณ  ์œ„ํ‚คํ”ผ๋””์•„๋ฅผ ์ฐธ๊ณ ํ•˜์—ฌ ์ž‘์„ฑํ–ˆ์Šต๋‹ˆ๋‹ค.


Data Structure, ์ž๋ฃŒ ๊ตฌ์กฐ๋ž€ ์ปดํ“จํ„ฐ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ํšจ์œจ์ ์œผ๋กœ ๊ด€๋ฆฌํ•˜๊ธฐ ์œ„ํ•ด ์ •์˜ํ•œ ์ž๋ฃŒ์˜ ๊ตฌ์กฐ์ฒด, ์กฐ์ง์„ ๋งํ•œ๋‹ค. ์ปดํ“จํ„ฐ ๋ฉ”๋ชจ๋ฆฌ์— ์ •๋ณด๋ฅผ ๊ฐ๊ธฐ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์œผ๋กœ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋„๋ก ํ•ด์ค€๋‹ค. ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋ฉ”๋ชจ๋ฆฌ์˜ ๋ ˆ์ด์•„์›ƒ์ด๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค. ๋ชฉ์ ์— ๋งž๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํšจ์œจ์„ฑ์„ ๋†’์—ฌ์ฃผ๊ธฐ ๋•Œ๋ฌธ์— ์ค‘์š”ํ•˜๋‹ค.

๋‹ค์–‘ํ•œ ์ž๋ฃŒ ๊ตฌ์กฐ ์ค‘

  • ๋ฐฐ์—ด
  • ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ
  • ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ
  • ํ•ด์‹œ ํ…Œ์ด๋ธ”

๋ฅผ ๊ฐ„๋‹จํ•˜๊ฒŒ ์‚ดํŽด๋ณด๊ฒ ๋‹ค.



๐Ÿ“š ๋ฐฐ์—ด (array)

๊ฐ™์€ ์ž๋ฃŒํ˜•์œผ๋กœ ๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์—ฐ์†์ ์œผ๋กœ ์ €์žฅํ•œ๋‹ค.

๐Ÿ’ก ์ธ๋ฑ์Šค๋ฅผ ์ด์šฉํ•ด ์›ํ•˜๋Š” ๊ฐ’์— ๋ฐ”๋กœ ์ ‘๊ทผ์ด ๊ฐ€๋Šฅํ•˜๋‹ค.

๐Ÿ“š ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ (Linked list)

๋ฉ”๋ชจ๋ฆฌ ๋ฉ์–ด๋ฆฌ ์—ฌ๋Ÿฌ๊ฐœ๋ฅผ ํฌํ•จํ•œ ๋ฐ์ดํ„ฐ๊ตฌ์กฐ, ๋…ธ๋“œ(node)๋ฅผ ๋‹จ์œ„๋กœ ํ•œ๋‹ค. ์ž๋ฃŒ์™€ ๋ฐ”๋กœ ๋‹ค์Œ ์ž๋ฃŒ์˜ ์ฃผ์†Œ (ํฌ์ธํ„ฐ)๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋‹ค.

๋‹จ์ผ ์—ฐ๊ฒฐ ๋ชฉ๋ก (Rune Magnussen, ์œ„ํ‚คํ”ผ๋””์•„)

๐Ÿ’ก ์žฅ์ 

์›๋ž˜ ์žˆ์—ˆ๋˜ ๋ฉ”๋ชจ๋ฆฌ์˜ ์œ„์น˜๋ฅผ ๋ณด์กดํ•˜๋ฉด์„œ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ถ”๊ฐ€ํ•  ์ˆ˜ ์žˆ๋‹ค.

๐Ÿ’ก ๋‹จ์ 

๋ฐฐ์—ด๊ณผ ๊ฐ™์ด ์ž„์˜ ์ ‘๊ทผ์ด ๋ถˆ๊ฐ€ํ•˜๋‹ค.


๐Ÿ“š ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ (Binary search tree)

์ด์ง„๊ฒ€์ƒ‰(Binary search)์™€ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ(Linked list)๊ฐ€ ๊ฒฐํ•ฉ๋œ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์ด๋‹ค. ๊ฐ ๋…ธ๋“œ๋“ค์€ ์ผ์ •ํ•œ ์ธต์— ์†ํ•˜๋ฉฐ, ๋‹ค์Œ ์ธต์˜ ๋…ธ๋“œ๋“ค์„ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ๋ฅผ ๊ฐ–๋Š”๋‹ค. ๊ฐ€์žฅ ๋†’์€ ์ธต์—์„œ ํŠธ๋ฆฌ๊ฐ€ ์‹œ์ž‘๋˜๋Š” ๋…ธ๋“œ๋ฅผ root๋ผ๊ณ  ํ•œ๋‹ค.

  • ๊ฐ ๋…ธ๋“œ์— ๊ฐ’์ด ์žˆ๋‹ค.
  • ๊ฐ’๋“ค์€ ์ „์ˆœ์„œ๊ฐ€ ์žˆ๋‹ค.
  • ๋…ธ๋“œ์˜ ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์—๋Š” ๊ทธ ๋…ธ๋“œ์˜ ๊ฐ’๋ณด๋‹ค ์ž‘์€ ๊ฐ’๋“ค์„ ์ง€๋‹Œ ๋…ธ๋“œ๋“ค๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค.
  • ๋…ธ๋“œ์˜ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์—๋Š” ๊ทธ ๋…ธ๋“œ์˜ ๊ฐ’๋ณด๋‹ค ํฐ ๊ฐ’๋“ค์„ ์ง€๋‹Œ ๋…ธ๋“œ๋“ค๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค.
  • ์ขŒ์šฐ ํ•˜์œ„ ํŠธ๋ฆฌ๋Š” ๊ฐ๊ฐ์ด ๋‹ค์‹œ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์—ฌ์•ผ ํ•œ๋‹ค.


๐Ÿ’ก ๊ฒ€์ƒ‰ ์‹คํ–‰ ์‹œ๊ฐ„๊ณผ ๋…ธ๋“œ ์‚ฝ์ž… ์‹œ๊ฐ„ ๋ชจ๋‘ O(log n)์ด๋‹ค.

๐Ÿ“š ํ•ด์‹œํ…Œ์ด๋ธ” (Hash table)

๋ฐฐ์—ด๊ณผ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๊ฐ€ ๊ฒฐํ•ฉ๋œ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์ด๋‹ค. ๊ฐ ์ž๋ฃŒ๋“ค์€ ํ•ด์‹œํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ์–ด๋–ค ๋ฐ”๊ตฌ๋‹ˆ์— ์†ํ• ์ง€ ์ •ํ•ด์ง„๋‹ค.


๐Ÿ’ก ๋งŒ์•ฝ ๋ฐ”๊ตฌ๋‹ˆ์— 1๊ฐœ์˜ ๊ฐ’์”ฉ๋งŒ ๋“ค์–ด์žˆ๋‹ค๋ฉด ๊ฒ€์ƒ‰์‹œ๊ฐ„์€ O(1)์ด๋‹ค. ํ•˜์ง€๋งŒ ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ์—๋Š” ๋‹จ ํ•˜๋‚˜์˜ ๋ฐ”๊ตฌ๋‹ˆ์— ๋ชจ๋“  ๊ฐ’๋“ค์ด ๋‹ด๊ฒจ์„œ O(n)์ด ๋  ์ˆ˜๋„ ์žˆ๋‹ค.

์ผ๋ฐ˜์ ์œผ๋กœ๋Š” ์ตœ๋Œ€ํ•œ ๋งŽ์€ ๋ฐ”๊ตฌ๋‹ˆ๋ฅผ ๋งŒ๋“œ๋Š” ํ•ด์‹œ ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๊ฑฐ์˜ O(1)์— ๊ฐ€๊น๋‹ค๊ณ  ๋ณผ ์ˆ˜ ์žˆ๋‹ค.



์ด ์™ธ์—๋„ ๋‹ค์–‘ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ๋“ค์ด ์žˆ๊ณ  ์‹ฌํ™” ๋‚ด์šฉ๋“ค์€ ์ถ”ํ›„ ๋ณด์ถฉํ•ด๊ฐ€๋ฉฐ ํ•™์Šตํ•˜๋„๋ก ํ•ด์•ผ๊ฒ ๋‹ค. ํ™”์ดํŒ…!๐Ÿฑโ€๐Ÿ‘“

profile
i๐ŸŽS ๊ฐœ๋ฐœ์„ ํ•ฉ๋‹ˆ๋‹ค

0๊ฐœ์˜ ๋Œ“๊ธ€