Skip to content

Juminhark/data_structure

Folders and files

NameName
Last commit message
Last commit date

Latest commit

ย 

History

2 Commits
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 

Repository files navigation

Data Structure(์ž๋ฃŒ๊ตฌ์กฐ) : Efficient access and modification

  • ํšจ์œจ์ ์œผ๋กœ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ ๊ตฌ์กฐํ™”๋œ data set

  • ๊ตฌ์กฐํ™”๋œ data set์€ service, application ์—์„œ ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ data๋ฅผ ํšจ์œจ์ ์ธ ๋ฐฉ์‹์œผ๋กœ ๋น ๋ฅด๊ฒŒ ์ ‘๊ทผ, ์ˆ˜์ •, ์‚ฝ์ž…, ์‚ญ์ œ ํ• ์ˆ˜์žˆ๋„๋ก ํ•œ๋‹ค.

  • ๋ชฉ์ ๊ณผ ํ•„์š”ํ•œ ๊ธฐ๋Šฅ์— ๋”ฐ๋ผ ์ ํ•ฉํ•œ data structure๊ฐ€ ์กด์žฌํ•œ๋‹ค.

    • service์—์„œ client์—๊ฒŒ data๋ฅผ ์ œ๊ณต => access, search ์— ์ค‘์ .
    • application์—์„œ user์—๊ฒŒ ํ•„์š”ํ•œ data๋ฅผ ๋ณด์—ฌ์ฃผ๊ฑฐ๋‚˜ ์ˆ˜์ • => access, modification์— ์ค‘์ 
  • data structure ๋งˆ๋‹ค ์‚ฌ์šฉ์ž๊ฐ€ ์›ํ•˜๋Š” ๊ธฐ๋Šฅ์„ ์ˆ˜ํ–‰ํ•˜๋Š”๋ฐ ์†๋„์˜ ์ฐจ์ด๊ฐ€ ๋‚ ์ˆ˜์žˆ๋‹ค.

  • ๋Œ€ํ‘œ์ ์œผ๋กœ Array, Linked-List, Double-Linked-List, Stack, Hash-Table ๋“ฑ.

  • data structure key point

    1. Order : structure์•ˆ์—์„œ data ์ˆœ์„œ ๋ณด์žฅ ์—ฌ๋ถ€
    1. Unique : ์ค‘๋ณต๋œ ๋ฐ์ดํ„ฐ ๊ฐ’์„ ๊ฐ€์งˆ์ˆ˜ ์žˆ๋Š”์ง€ ์—ฌ๋ถ€
    1. Search : ๊ฒ€์ƒ‰์˜ ํšจ์œจ์„ฑ
    1. Modification : ๋ฐ์ดํ„ฐ ์ˆ˜์ •์˜ ํšจ์œจ์„ฑ

๋ถ„๋ฅ˜

๊ตฌํ˜„์— ๋”ฐ๋ผ

  • ๋ฐฐ์—ด
  • ํŠœํ”Œ
  • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ
  • ์›ํ˜• ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ
  • ์ด์ค‘ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ
  • ํ•ด์‹œ ํ…Œ์ด๋ธ”

ํ˜•ํƒœ์— ๋”ฐ๋ผ

  • ์„ ํ˜•๊ตฌ์กฐ
    • ์ •์  ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ
      • ๋ฐฐ์—ด
    • ๋™์  ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ
      • ์Šคํƒ
      • ํ
      • ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ
  • ๋น„์„ ํ˜• ๊ตฌ์กฐ
    • ๊ทธ๋ž˜ํ”„
    • ํŠธ๋ฆฌ
      • ์ด์ง„ ํŠธ๋ฆฌ
        • ํž™

What are data structures

  • ๋†’์€ ์ˆ˜์ค€์˜ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋Š” ์ˆ˜์ •, ํƒ์ƒ‰, ์ ‘๊ทผ์„ ๋ณด๋‹ค ์‰ฝ๊ฒŒ ํ•ด์ฃผ๋Š” ๋ฐ์ดํ„ฐ ์ €์žฅ ๋ฐ ๊ตฌ์„ฑ ๊ธฐ์ˆ ์ž…๋‹ˆ๋‹ค.

  • ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋Š” ๋ฐ์ดํ„ฐ ์ˆ˜์ง‘ ๋ฐฉ๋ฒ•, ๋ฐ์ดํ„ฐ์— ์ ‘๊ทผํ•˜๋Š”๋ฐ ์‚ฌ์šฉํ• ์ˆ˜ ์žˆ๋Š” ๊ธฐ๋Šฅ ๋ฐ ๋ฐ์ดํ„ฐ ๊ฐ„์˜ ๊ด€๊ณ„๋ฅผ ๊ฒฐ์ •ํ•ฉ๋‹ˆ๋‹ค.

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

  • ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋Š” ์šฐ๋ฆฌ๊ฐ€ ๋‹ค์Œ๊ณผ ๊ฐ™์€๊ฒƒ๋“ค์ด ๊ฐ€๋Šฅํ•˜๊ฒŒํ•ฉ๋‹ˆ๋‹ค.

      1. ๋Œ€๊ทœ๋ชจ์˜ ์ž๋ฃŒ์ง‘ํ•ฉ์˜ ๊ด€๋ฆฌ ๋ฐ ํ™œ์šฉ
      1. ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์—์„œ ํŠน์ •ํ•œ ๋ฐ์ดํ„ฐ ํƒ์ƒ‰
      1. ํŠน์ • ํ”„๋กœ๊ทธ๋žจ์— ๋งž๋Š” ์„ค๊ณ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜
      1. ์‚ฌ์šฉ์ž๋“ค์˜ ์—ฌ๋Ÿฌ ์š”์ฒญ์„ ํ•œ ๋ฒˆ์— ์ฒ˜๋ฆฌ
      1. ๋ฐ์ดํ„ฐ ์ฒ˜๋ฆฌ ๋‹จ์ˆœํ™” ๋ฐ ์†๋„ ํ–ฅ์ƒ
  • ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋Š” ํšจ์œจ์ ์ธ ์‹ค์ œ์ ์ธ ๋ฌธ์ œ ํ•ด๊ฒฐ์— ํ•„์ˆ˜์ ์ด๋‹ค.

  • ๋ฌด์—‡๋ณด๋‹ค ์šฐ๋ฆฌ๊ฐ€ ๋ฐ์ดํ„ฐ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ๋ฐฉ์‹์€ ์„ฑ๋Šฅ๊ณผ ์œ ์šฉ์„ฑ์— ๋งŽ์€ ์˜ํ–ฅ์„ ๋ฏธ์นฉ๋‹ˆ๋‹ค.

  • ์‹ค์ œ๋กœ ๋Œ€๋ถ€๋ถ„์˜ ์ตœ๊ณ  ๊ธฐ์—…์€ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์— ๋Œ€ํ•œ ๊ฐ•๋ ฅํ•œ ์ดํ•ด๋ฅผ ํ•„์š”๋กœํ•ฉ๋‹ˆ๋‹ค.

  • ์ด๋Ÿฌํ•œ ๊ธฐ์ˆ ์€ ๋‹น์‹ ์ด ๋‹น์‹ ์˜ ๋ฐ์ดํ„ฐ๋ฅผ ํšจ๊ณผ์ ์œผ๋กœ ๊ด€๋ฆฌํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ดํ•ดํ•˜๋Š”์ง€๋ฅผ ์ฆ๋ช…ํ•ฉ๋‹ˆ๋‹ค.

  • ์ฝ”๋”ฉ ์ธํ„ฐ๋ทฐ๋ฅผ ๊นจ๋ถ€์‹ค๋ คํ•˜๋Š” ์‚ฌ๋žŒ์€ ๋ˆ„๊ตฌ๋‚˜ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ ์ˆ™๋‹ฌ์„ ํ•„์š”๋กœ ํ•œ๋‹ค.

  • JavaScript์—๋Š” ๊ธฐ๋ณธ(์›์‹œ) ๋ฐ ๋น„ ๊ธฐ๋ณธ(์›์‹œ) ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

  • ๊ธฐ๋ณธ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ ๋ฐ ๋ฐ์ดํ„ฐ ์œ ํ˜•์€ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด์— ๊ธฐ๋ณธ์œผ๋กœ ์ œ๊ณต๋ฉ๋‹ˆ๋‹ค.

  • ์—ฌ๊ธฐ์—๋Š” boolean, null, number, string, ๊ธฐํƒ€๋“ฑ๋“ฑ์ด ํฌํ•จ๋œ๋‹ค.

  • ๊ธฐ๋ณธ์ด ์•„๋‹Œ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋Š” ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด๊ฐ€ ์•„๋‹ˆ๋ผ ํ”„๋กœ๊ทธ๋ž˜๋จธ์— ์˜ํ•ด ์ •์˜๋ฉ๋‹ˆ๋‹ค.

  • ์—ฌ๊ธฐ์—๋Š” ์„ ํ˜• ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ, ์ •์  ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ, queue ๋ฐ linked-list์™€ ๊ฐ™์€ ๋™์  ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๊ฐ€ ํฌํ•จ๋ฉ๋‹ˆ๋‹ค.

  • ์„ ํ˜• : linked-list, stack, queue

  • ๋น„์„ ํ˜• : tree, graph

7 JavaScript data structures

    1. Array
    • ๋ชจ๋“  ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ ์ค‘ ๊ฐ€์žฅ ๊ธฐ๋ณธ์ ์ธ ๋ฐฐ์—ด์€ ๋‚˜์ค‘์— ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋„๋ก ๋ฐ์ดํ„ฐ๋ฅผ ๋ฉ”๋ชจ๋ฆฌ์— ์ €์žฅํ•ฉ๋‹ˆ๋‹ค.
    • ๊ฐ ๋ฐฐ์—ด์—๋Š” ์ƒ์„ฑ์‹œ ๊ฒฐ์ •๋œ ๊ณ ์ • ๋œ ์ˆ˜์˜ ์…€์ด ์žˆ์œผ๋ฉฐ ๊ฐ ์…€์—๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์„ ํƒํ•˜๋Š” ๋ฐ ์‚ฌ์šฉ๋˜๋Š” ํ•ด๋‹น ์ˆซ์ž ์ธ๋ฑ์Šค๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ๋ฐฐ์—ด๋ฅผ ์‚ฌ์šฉํ•˜๊ณ  ์‹ถ์„ ๋•Œ๋งˆ๋‹ค ์›ํ•˜๋Š” ์ธ๋ฑ์Šค ๋งŒ ์žˆ์œผ๋ฉด๋˜๊ณ  ๊ทธ ์•ˆ์˜ ๋ชจ๋“  ๋ฐ์ดํ„ฐ์— ์ ‘๊ทผ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ์žฅ์  : ๋ณต์žกํ•œ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋ฅผ์œ„ํ•œ ๊ธฐ๋ณธ ๊ตฌ์„ฑ ์š”์†Œ๋กœ์„œ ์ƒ์„ฑ ๋ฐ ์‚ฌ์šฉ์ด ๊ฐ„๋‹จ
    • ๋‹จ์  : ๊ณ ์ •ํฌ๊ธฐ, ๋น„ํšจ์œจ์ ์ธ ๋ถ„๋ฅ˜, ๊ฐ’์„ ์‚ฝ์ž… / ์‚ญ์ œํ•˜๊ฑฐ๋‚˜ ๋‹ค์‹œ ์ •๋ ฌํ•˜๋Š” ๋ฐ ๋งŽ์€ ๋น„์šฉ์ด ๋“ญ๋‹ˆ๋‹ค.
    • ํ™œ์šฉ : ๊ธฐ๋ณธ์ ์ธ spreadsheets ์—์„œ ์‚ฌ์šฉํ•˜๊ฑฐ๋‚˜, ํ•ด์‹œ ํ…Œ์ด๋ธ”๊ณผ ๊ฐ™์€ ๋ณต์žกํ•œ ๊ตฌ์กฐ ๋‚ด์—์„œ ์‚ฌ์šฉ.
    1. Stack & Queues
    • ๋‘˜๋‹ค ์ˆœ์ฐจ์  ๊ตฌ์กฐ
    • Stack : LIFO(Last In First Out) : ํ›„์ž…์„ ์ถœ : ๋‚˜์ค‘์— ๋“ค์–ด์˜จ๊ฒƒ์ด ๋จผ์ € ๋‚˜๊ฐ„๋‹ค
    • Queue : FIFO(First In First OUT) : ์„ ์ž…์„ ์ถœ : ๋จผ์ € ๋“ค์–ด์˜จ๊ฒƒ์ด ๋จผ์ € ๋‚˜๊ฐ„๋‹ค
    • ์žฅ์  : ๋™์  ํฌ๊ธฐ, ๋‚ฎ์€ ๋Ÿฐํƒ€์ž„
    • ๋‹จ์  : ๊ฐ€์žฅ์˜ค๋ž˜๋œ, ๊ฐ€์žฅ ์ตœ๊ทผ ์š”์†Œ๋งŒ ๊ฒ€์ƒ‰ํ• ์ˆ˜์žˆ๋‹ค.
    • ํ™œ์šฉ : ํ•œ๋ฒˆ์— 1๊ฐ€์ง€ ์ฒ˜๋ฆฌ๋ฅผํ• ๋•Œ ์ฒ˜๋ฆฌ ๋Œ€์ƒ์˜ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ์žˆ๋Š”๊ฒฝ์šฐ
    1. Linked List
    • ๋ฉ”๋ชจ๋ฆฌ์—์„œ ๋ฌผ๋ฆฌ์  ๋ฐฐ์น˜๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ.
    • ์ฆ‰, Linked List๋Š” ์ƒ‰์ธ์ด๋‚˜ ์œ„์น˜๊ฐ€ ์•„๋‹Œ ์ฐธ์กฐ ์‹œ์Šคํ…œ์„ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.
    • ์š”์†Œ๋Š” ๋‹ค์Œ ๋…ธ๋“œ์— ๋Œ€ํ•œ ํฌ์ธํ„ฐ๋ฅผ ํฌํ•จํ•˜๋Š” ๋…ธ๋“œ์— ์ €์žฅ๋˜๋ฉฐ ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ๋งํฌ ๋  ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณต๋ฉ๋‹ˆ๋‹ค.
    • ์ด ์‹œ์Šคํ…œ์„ ์‚ฌ์šฉํ•˜๋ฉด ์žฌ๊ตฌ์„ฑ ํ•  ํ•„์š”์—†์ด ํ•ญ๋ชฉ์„ ํšจ์œจ์ ์œผ๋กœ ์‚ฝ์ž…ํ•˜๊ณ  ์ œ๊ฑฐ ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ์žฅ์  : ์ƒˆ๋กœ์šด ์š”์†Œ์˜ ํšจ์œจ์ ์ธ ์‚ฝ์ž… ๋ฐ ์ œ๊ฑฐ, array ์žฌ๊ตฌ์„ฑ๋ณด๋‹ค ๋œ ๋ณต์žก
    • ๋‹จ์  : ๋ฐฐ์—ด๋ณด๋‹ค ๋” ๋งŽ์€ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉ,ํŠน์ • ์š”์†Œ๋ฅผ ๊ฒ€์ƒ‰ํ•˜๋Š” ๋ฐ ๋น„ํšจ์œจ์ , ๋ชฉ๋ก์„ ๋’ค๋กœ ํƒ์ƒ‰ํ•˜๋Š” ๊ฒƒ์€ ๋น„ํšจ์œจ์ 
    • ํ™œ์šฉ : ์•Œ ์ˆ˜์—†๋Š” ์œ„์น˜์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์—ฐ์†์ ์œผ๋กœ ๋น ๋ฅด๊ฒŒ ์ถ”๊ฐ€ ๋ฐ ์ œ๊ฑฐํ•ด์•ผ ํ•  ๋•Œ ๊ฐ€์žฅ ์ ํ•ฉ
    1. Trees
    • Trees๋Š” ํšŒ์‚ฌ ์ง์› ์กฐ์ง ๊ตฌ์กฐ์™€ ๊ฐ™์€ ๊ณ„์ธต ๊ตฌ์กฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐ ํŠนํ™”๋œ ๊ด€๊ณ„ ๊ธฐ๋ฐ˜ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ(๋น„์„ ํ˜• ๊ตฌ์กฐ)์ž…๋‹ˆ๋‹ค.

    • Linked List์™€ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๋…ธ๋“œ์—๋Š” ๋ฐ์ดํ„ฐ ์š”์†Œ์™€ ์ง์ ‘ ๋…ธ๋“œ์™€์˜ ๊ด€๊ณ„๋ฅผ ํ‘œ์‹œํ•˜๋Š” ํฌ์ธํ„ฐ๊ฐ€ ๋ชจ๋‘ ํฌํ•จ๋ฉ๋‹ˆ๋‹ค.

    • ๊ฐ ํŠธ๋ฆฌ์—๋Š” ๋‹ค๋ฅธ ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ๋ถ„๊ธฐ๋˜๋Š” "๋ฃจํŠธ"๋…ธ๋“œ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.

    • ๋ฃจํŠธ์—๋Š” "ํ•˜์œ„ ๋…ธ๋“œ"๋ผ๊ณ ํ•˜๋Š” ๋ฐ”๋กœ ์•„๋ž˜์—์žˆ๋Š” ๋ชจ๋“  ์š”์†Œ์— ๋Œ€ํ•œ ์ฐธ์กฐ๊ฐ€ ํฌํ•จ๋ฉ๋‹ˆ๋‹ค.

    • ์ด๊ฒƒ์€ ๊ฐ ์ž์‹ ๋…ธ๋“œ์™€ ํ•จ๊ป˜ ๋” ๋งŽ์€ ์ž์‹ ๋…ธ๋“œ๋กœ ๋ถ„๊ธฐ๋ฉ๋‹ˆ๋‹ค.

    • ์—ฐ๊ฒฐ๋œ ์ž์‹ ๋…ธ๋“œ๊ฐ€์žˆ๋Š” ๋…ธ๋“œ๋ฅผ ๋‚ด๋ถ€ ๋…ธ๋“œ๋ผ๊ณ ํ•˜๋ฉฐ ์ž์‹ ๋…ธ๋“œ๊ฐ€์—†๋Š” ๋…ธ๋“œ๋Š” ์™ธ๋ถ€ ๋…ธ๋“œ๋ผ๊ณ ํ•ฉ๋‹ˆ๋‹ค.

    • ์ผ๋ฐ˜์ ์ธ ์œ ํ˜•์˜ ํŠธ๋ฆฌ๋Š” ์ €์žฅ๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์‰ฝ๊ฒŒ ๊ฒ€์ƒ‰ํ•˜๋Š” ๋ฐ ์‚ฌ์šฉ๋˜๋Š” binary search tree ์ž…๋‹ˆ๋‹ค.

    • ์ด๋Ÿฌํ•œ ๊ฒ€์ƒ‰ ์ž‘์—…์€ ๊ฒ€์ƒ‰ ๊ธฐ๊ฐ„์ด ๋…ธ๋“œ ์ˆ˜๊ฐ€ ์•„๋‹ˆ๋ผ ํŠธ๋ฆฌ ์•„๋ž˜์˜ ์ˆ˜์ค€ ์ˆ˜์— ๋”ฐ๋ผ ๋‹ฌ๋ผ ์ง€๋ฏ€๋กœ ๋งค์šฐ ํšจ์œจ์ ์ž…๋‹ˆ๋‹ค.

    • ์žฅ์  : ๊ณ„์ธต์ ๊ด€๊ณ„์ €์žฅ์— ์ด์ƒ์ . ๋™์ ํฌ๊ธฐ. ๋น ๋ฅธ ์‚ฝ์ž…, ์‚ญ์ œ.

    • ์ด์ง„๊ฒ€์ƒ‰ํŠธ๋ฆฌ๋Š” ๊ฒ€์ƒ‰์— ํšจ์œจ์ . ์‹œ๊ฐ„๋ณต์žก๋„ : O(height)

    • ๋‹จ์  : ์žฌ๋ฐฐ์—ด ์†๋„๊ฐ€ ๋А๋ฆฌ๋‹ค. ์ž์‹ ๋…ธ๋“œ์—๊ฒŒ ๋ถ€๋ชจ๋…ธ๋“œ์˜ ์ •๋ณด๊ฐ€ ์—†๋‹ค. ํ•ด์‹œํ…Œ์ด๋ธ”๋ณด๋‹ค ๋น„๊ต์  ๋А๋ฆฌ๋‹ค.

    1. Graphs
    • ๊ด€๊ณ„ ๊ธฐ๋ฐ˜ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ.
    • ๊ทธ๋ž˜ํ”„์—์„œ ํ˜ธ์ถœ๋˜๋Š” ๊ฐ ๋…ธ๋“œ ๋˜๋Š” ์ •์ ์—๋Š” ์ œ๋ชฉ (A, B, C ๋“ฑ), ๋‚ด๋ถ€์— ํฌํ•จ ๋œ ๊ฐ’ ๋ฐ ๋‹ค๋ฅธ ์ •์ ๊ณผ์˜ ๋งํฌ ๋ชฉ๋ก(edges))์ด ์žˆ์Šต๋‹ˆ๋‹ค.
    • ๊ด€๊ณ„ : Undirected(์–‘๋ฐฉํ†ตํ–‰), Directed(๋ฐฉํ–ฅ์„ฑ)
    • ์ฒ˜์Œ์—๋Š” ์‹œ๊ฐํ™”ํ•˜๊ธฐ ์–ด๋ ต์ง€๋งŒ, ์ด ๊ตฌ์กฐ๋Š” ํšŒ๋กœ์—์„œ ํ›ˆ๋ จ ๋„คํŠธ์›Œํฌ์— ์ด๋ฅด๊ธฐ๊นŒ์ง€ ๊ด€๊ณ„ ์ฐจํŠธ๋ฅผ ํ…์ŠคํŠธ ํ˜•์‹์œผ๋กœ ์ „๋‹ฌํ•˜๋Š” ๋ฐ ๋งค์šฐ ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.
  • ๊ผญ์ง“์ , ์ •์  : vertex(vertices), node(nodes)

  • ๋ณ€, ๊ฐ„์„  : edge

  • adjacent vertex(์ธ์ ‘์ •์ ) : edge๋กœ ์—ฐ๊ฒฐ๋œ vertex

  • degree(์ฐจ์ˆ˜-๋“ฑ๊ธ‰-๊ณ„๊ธ‰)

      1. undirected graph ์—์„œ๋Š” ์—ฐ๊ฒฐ๋œ edge์˜ ์ˆ˜
      1. directed graph ์—์„œ๋Š” vertex ๊ธฐ์ค€.
      • in-degree : ์ž…๋ ฅ์ฐจ์ˆ˜ : vertex๊ฐ€ ๋ฐฉํ–ฅ์˜ ๋Œ€์ƒ์ด ๋˜๋Š” edge์˜ ์ˆ˜
      • out-degree : ์ถœ๋ ฅ์ฐจ์ˆ˜ : vertex๊ฐ€ ์‹œ์ž‘์˜ ๋Œ€์ƒ์ด ๋˜๋Š” edge์˜ ์ˆ˜
  • cycle : vertex๊ฐ€ ๊ฒฝ๋กœ์˜ ์ถœ๋ฐœ์ž„๊ณผ ๋™์‹œ์— ๋„์ฐฉ์˜ ๋Œ€์ƒ์ด ๋  ๊ฒฝ์šฐ

  • complete graph : ๋ชจ๋“  vertex๊ฐ€ ์„œ๋กœ directํ•˜๊ฒŒ adjacent vertex ์ธ ๊ฒฝ์šฐ

  • weighted graph : edge์— ๊ฐ€์ค‘์น˜๊ฐ€ ์กด์žฌํ• ๊ฒฝ์šฐ

  • ์žฅ์  : ํ…์ŠคํŠธ๋ฅผ ํ†ตํ•ด ์‹œ๊ฐ์ ์œผ๋กœ ๋น ๋ฅด๊ฒŒ ์ „๋‹ฌ, ๋งŽ์€ ์ •๋ณด๋ฅผ ํฌํ•จํ•˜๊ณ  ์žˆ๋Š” ๊ด€๊ณ„ํ˜• ๊ตฌ์กฐ๋ฅผ ํ‘œํ˜„ํ•ด์•ผํ•˜๋Š” ์ฃผ์ œ์— ์ ํ•ฉ

  • ๋‹จ์  : ๋†’์€ ์ˆ˜์ค€์—์„œ๋Š” ํ…์ŠคํŠธ๋ฅผ ์ด๋ฏธ์ง€ํ™” ํ•˜๊ธฐ ์–ด๋ ต๋‹ค.

  • ํ™œ์šฉ : ๋„คํŠธ์›Œํฌ ํ‘œํ˜„

    1. Hash Tables (Map)

Reference

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published