๊ฐœ์ธ ๊ณต๋ถ€ ๊ณผ์ •์„ ๊ธฐ๋กํ•ฉ๋‹ˆ๋‹ค.

๐Ÿš€ What I Will Learn

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

์ž๋ฃŒ๊ตฌ์กฐ์˜ ๊ฐœ์š”

1๏ธโƒฃ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ํ•„์š”์„ฑ

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

์˜ˆ์‹œ) ํ”„๋กœ๊ทธ๋žจ ๋‚ด์—์„œ INTํ˜• ๋ฐ์ดํ„ฐ๊ฐ€ 1์–ต๊ฐœ ๊ฐ€๋Ÿ‰ ์‚ฌ์šฉ๋œ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž. ์ด๋•Œ ์›ํ•˜๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์žฅ ๋น ๋ฅด๊ฒŒ ์ฐพ๋„๋ก ํ•ด์ฃผ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋ฌด์—‡์ธ๊ฐ€?


โœ”๏ธ ๊ธฐ๋ณธ์ ์ธ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ํ˜•ํƒœ

  1. ์„ ํ˜• ๊ตฌ์กฐ
  • ๋ฐฐ์—ด
  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ
  • ์Šคํƒ
  • ํ
  1. ๋น„์„ ํ˜• ๊ตฌ์กฐ
  • ํŠธ๋ฆฌ(Tree)
  • ๊ทธ๋ž˜ํ”„(Graph)


โœ”๏ธ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ƒ๊ด€ ๊ด€๊ณ„?!

  • ํšจ์œจ์ ์ธ ์ž๋ฃŒ๊ตฌ์กฐ ์„ค๊ณ„๋ฅผ ์œ„ํ•ด ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ง€์‹์ด ํ•„์š”
  • ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ž‘์„ฑํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋ฌธ์ œ ์ƒํ™ฉ์— ๋งž๋Š” ์ ์ ˆํ•œ ์ž๋ฃŒ๊ตฌ์กฐ ์‚ฌ์šฉ ํ•„์š”

์ฆ‰, ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋–ผ๋ ค์•ผ ๋—„ ์ˆ˜ ์—†๋Š” ๊ด€๊ณ„์ด๋‹ค!


โœ”๏ธ ํ”„๋กœ๊ทธ๋žจ์˜ ์„ฑ๋Šฅ ์ธก์ • ๋ฐฉ๋ฒ•๋ก 

  • ์‹œ๊ฐ„ ๋ณต์žก๋„(Time Complexity)๋ž€?
    • ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์‚ฌ์šฉ๋˜๋Š” ์—ฐ์‚ฐ ํšŸ์ˆ˜๋ฅผ ์˜๋ฏธ
  • ๊ณต๊ฐ„ ๋ณต์žก๋„(Space Complexity)๋ž€?
    • ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์‚ฌ์šฉ๋˜๋Š” ๋ฉ”๋ชจ๋ฆฌ ์–‘์„ ์˜๋ฏธ

์ฆ‰, ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•œ๋‹ค๊ณ  ๊ฐ€์ •ํ–ˆ์„ ๋•Œ, ์ผ๋ฐ˜์ ์œผ๋กœ ์‹œ๊ฐ„๊ณผ ๊ณต๊ฐ„์€ ๋ฐ˜๋น„๋ก€ ๊ด€๊ณ„์ด๋‹ค

๐Ÿ“Œ ์ฐธ๊ณ ! ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ํ‘œํ˜„ํ•  ๋•Œ๋Š” ์ตœ์•…์˜ ๊ฒฝ์šฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” Big-O ํ‘œ๊ธฐ๋ฒ•์„ ์‚ฌ์šฉํ•œ๋‹ค.

  • ํ”„๋กœ๊ทธ๋žจ ์„ฑ๋Šฅ ์ธก์ • ๋ฐฉ๋ฒ•๋ก  ์˜ˆ์‹œ ์ด๋ฏธ์ง€:
    • ๋ณดํ†ต ์—ฐ์‚ฐ ํšŸ์ˆ˜๊ฐ€ 10์–ต์„ ๋„˜์–ด๊ฐ€๋ฉด 1์ดˆ ์ด์ƒ์˜ ์‹œ๊ฐ„์ด ์†Œ์š”๋œ๋‹ค.


๐Ÿ“Œ ์ฐธ๊ณ ! ๊ณต๊ฐ„ ๋ณต์žก๋„๋ฅผ ํ‘œ๊ธฐํ•  ๋•Œ๋Š” ์ผ๋ฐ˜์ ์œผ๋กœ MB ๋‹จ์œ„๋กœ ํ‘œ๊ธฐํ•œ๋‹ค

  • int a[1000]: 4KB
  • int a[1000000]: 4MB
  • int a[2000][2000]: 16MB




โœจ tl;dr

  • ์ž๋ฃŒ๊ตฌ์กฐ์˜ ์ข…๋ฅ˜๋Š” ์Šคํƒ, ํ, ํŠธ๋ฆฌ ๋“ฑ์ด ์žˆ๋‹ค
  • ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•  ๋•Œ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ ์ ˆํžˆ ํ™œ์šฉํ•˜์—ฌ ์„ฑ๋Šฅ ์ตœ์ ํ™”๋ฅผ ๋…ธ๋ ค์•ผ ํ•œ๋‹ค