8000 GitHub - oiosu/codingtest_pass: ๐Ÿ”ฅ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๐Ÿ”ฅ
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

oiosu/codingtest_pass

Folders and files

NameName
Last commit message
Last commit date

Latest commit

ย 

History

75 Commits
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 

Repository files navigation

โœ” ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๋Œ€๋น„ ์ž๋ฃŒ๊ตฌ์กฐ ๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ TIL


๐Ÿ“Œ ์ž๋ฃŒ๊ตฌ์กฐ

Array ๋ฐฐ์—ด, Queue ํ, Stack ์Šคํƒ, Linked List ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ, Hash ํ•ด์‰ฌ, Tree ํŠธ๋ฆฌ, Heap ํž™


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

image

๐Ÿ’ก Array BAJ TIL

2750 2751 10989 25305 2108 1427 11650 11651 1181 10814 18870


  • ๊ฐ€์žฅ ๋จผ์ € ๋„ฃ์€ ๋ฐ์ดํ„ฐ๋ฅผ ๋จผ์ € ๊บผ๋‚ผ ์ˆ˜ ์žˆ๋Š” ๊ตฌ์กฐ
  • ๋†€์ด๊ณต์›์„œ ๊ฐ€์žฅ ๋จผ์ € ์ค„์„ ์„  ์‚ฌ๋žŒ์ด ์ œ์ผ ๋จผ์ € ์ž…์žฅํ•˜๋Š” ๊ฒƒ๊ณผ ๋™์ผ
  • FIFO ๋˜๋Š” LILO ๋ฐฉ์‹์œผ๋กœ ์Šคํƒ๊ณผ ๊บผ๋‚ด๋Š” ์ˆœ์„œ๊ฐ€ ๋ฐ˜๋Œ€
  • Enqueue : ํ์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๋Š” ๊ธฐ๋Šฅ (= put)
  • Dequeue: ํ์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ๊บผ๋‚ด๋Š” ๊ธฐ๋Šฅ (=get)

image image

๐Ÿ’ก Queue BAJ TIL

18258 2164 11866 1966 10866 1021 5430


  • ๋ฐ์ดํ„ฐ๋ฅผ ์ œํ•œ์ ์œผ๋กœ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๋Š” ๊ตฌ์กฐ (ํ•œ์ชฝ ๋์—์„œ๋งŒ ์ž๋ฃŒ๋ฅผ ๋„ฃ๊ฑฐ๋‚˜ ๋บผ ์ˆ˜ ์žˆ๋Š” ๊ตฌ์กฐ )

  • ๊ฐ€์žฅ ๋‚˜์ค‘์— ์Œ“์€ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์žฅ ๋จผ์ € ๋นผ๋‚ผ ์ˆ˜ ์žˆ๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ (ํ FIFO vs ์Šคํƒ LIFO)

  • ๋Œ€ํ‘œ์  ํ™œ์šฉ : ์ปดํ“จํ„ฐ ๋‚ด๋ถ€์˜ ํ”„๋กœ์„ธ์Šค ๊ตฌ์กฐ์˜ ํ•จ์ˆ˜ ๋™์ž‘ ๋ฐฉ์‹

  • push() : ๋ฐ์ดํ„ฐ๋ฅผ ์Šคํƒ์— ๋„ฃ๊ธฐ pop() : ๋ฐ์ดํ„ฐ๋ฅผ ์Šคํƒ์—์„œ ๊บผ๋‚ด๊ธฐ

image

image

๐Ÿ’ก Stack BAJ TIL

10828 10773 9012 4949 1874 17298


image

  • Linked List VS Array
    • ๋ฐฐ์—ด์€ ์ˆœ์ฐจ์ ์œผ๋กœ ์—ฐ๊ฒฐ๋œ ๊ณต๊ฐ„์— ๋ฐ์ดํ„ฐ๋ฅผ ๋‚˜์—ดํ•˜๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ
    • ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ๋Š” ๋–จ์–ด์ง„ ๊ณณ์— ์กด์žฌํ•˜๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ํ™”์‚ดํ‘œ๋กœ ์—ฐ๊ฒฐํ•ด์„œ ๊ด€๋ฆฌํ•˜๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ
    • C์–ธ์–ด๋Š” ์ฃผ์š”ํ•œ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์ด์ง€๋งŒ ํŒŒ์ด์ฌ์€ ๋ฆฌ์ŠคํŠธ ํƒ€์ž…์ด ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์˜ ๊ธฐ๋Šฅ์„ ๋ชจ๋‘ ์ง€์›

image

  • NODE : ๋ฐ์ดํ„ฐ ์ €์žฅ๋‹จ์œ„ (๋ฐ์ดํ„ฐ ๊ฐ’, ํฌ์ธํ„ฐ)๋กœ ๊ตฌ์„ฑ (๊ตฌํ˜„ ์‹œ ํŒŒ์ด์ฌ ๊ฐ์ฒด์ง€ํ–ฅ ๋ฌธ๋ฒ• ์ดํ•ด ํ•„์š”)
  • Pointer : ๊ฐ ๋…ธ๋“œ ์•ˆ์—์„œ, ๋‹ค์Œ์ด๋‚˜ ์ด์ „์˜ ๋…ธ๋“œ์™€์˜ ์—ฐ๊ฒฐ ์ •๋ณด๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๊ณต๊ฐ„

โ—ผ ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ์˜ ์žฅ๋‹จ์ 

์žฅ์  ๋‹จ์  _ ์ผ๋ฐ˜์ ์ธ ์Šคํƒ ๊ตฌํ˜„ ์‹œ
๋ฏธ๋ฆฌ ๋ฐ์ดํ„ฐ ๊ณต๊ฐ„์„ ๋ฏธ๋ฆฌ ํ• ๋‹นํ•˜์ง€ ์•Š์•„๋„ ๋จ ์—ฐ๊ฒฐ์„ ์œ„ํ•œ ๋ณ„๋„ ๋ฐ์ดํ„ฐ ๊ณต๊ฐ„์ด ํ•„์š”ํ•˜๋ฏ€๋กœ, ์ €์žฅ ๊ณต๊ฐ„ ํšจ์œจ์ด ๋†’์ง€ ์•Š์Œ
(๋ฐ˜๋ฉด, ๋ฐฐ์—ด์€ ๋ฏธ๋ฆฌ ๋ฐ์ดํ„ฐ ๊ณต๊ฐ„์„ ํ• ๋‹นํ•ด์•ผํ•˜๋Š” ์ ์ด ์žˆ๋‹ค.) ์—ฐ๊ฒฐ ์ •๋ณด๋ฅผ ์ฐพ๋Š” ์‹œ๊ฐ„์ด ํ•„์š”ํ•˜๋ฏ€๋กœ ์ ‘๊ทผ ์†๋„๊ฐ€ ๋А๋ฆฌ๋‹ค.
- ์ค‘๊ฐ„ ๋ฐ์ดํ„ฐ ์‚ญ์ œ์‹œ, ์•ž๋’ค ๋ฐ์ดํ„ฐ์˜ ์—ฐ๊ฒฐ์„ ์žฌ๊ตฌ์„ฑํ•ด์•ผ ํ•˜๋Š” ๋ถ€๊ฐ€์ ์ธ ์ž‘์—… ํ•„์š”

ํ•ด์‰ฌ Hash ์ž„์˜ ๊ฐ’์„ ๊ณ ์ • ๊ธธ์ด๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ๊ฒƒ
ํ•ด์‰ฌ ํ…Œ์ด๋ธ” Hash Table ํ‚ค ๊ฐ’์˜ ์—ฐ์‚ฐ์— ์˜ํ•ด ์ง์ ‘ ์ ‘๊ทผ์ด ๊ฐ€๋Šฅํ•œ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ
ํ•ด์‹ฑ ํ•จ์ˆ˜ Hashing Function Key์— ๋Œ€ํ•ด ์‚ฐ์ˆ  ์—ฐ์‚ฐ์„ ์ด์šฉํ•ด ๋ฐ์ดํ„ฐ ์œ„์น˜๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ๋Š” ํ•จ์ˆ˜
ํ•ด์‰ฌ ๊ฐ’ Hash Vale Key๋ฅผ ํ•ด์‹ฑ ํ•จ์ˆ˜๋กœ ์—ฐ์‚ฐํ•ด์„œ, ํ•ด์‰ฌ ๊ฐ’์„ ์•Œ์•„๋‚ด๊ณ , ์ด๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•ด์‰ฌ ํ…Œ์ด๋ธ”์—์„œ ํ•ด๋‹น Key์— ๋Œ€ํ•œ ๋ฐ์ดํ„ฐ ์œ„์น˜๋ฅผ ์ผ๊ด€์„ฑ์žˆ๊ฒŒ ์ฐพ์„ ์ˆ˜ ์žˆ์Œ
์Šฌ๋กฏ Slot ํ•œ ๊ฐœ์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋Š” ๊ณต๊ฐ„

image

๐Ÿ’ก Hash BAJ TIL

15829


  • Node์™€ Branch๋ฅผ ์ด์šฉํ•ด์„œ ์‚ฌ์ดํด์„ ์ด๋ฃจ์ง€ ์•Š๋„๋ก ๊ตฌ์„ฑํ•œ ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ
  • ์–ด๋””์— ์‚ฌ์šฉ?
    • ํŠธ๋ฆฌ ์ค‘ ์ด์ง„ํŠธ๋ฆฌ์˜ ํ˜•ํƒœ์˜ ๊ตฌ์กฐ๋กœ, ํƒ์ƒ‰(๊ฒ€์ƒ‰)์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„์„ ์œ„ํ•ด ๋งŽ์ด ์‚ฌ์šฉ๋œ๋‹ค.

image

  • Node: ํŠธ๋ฆฌ์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋Š” ๊ธฐ๋ณธ ์š”์†Œ (๋ฐ์ดํ„ฐ์™€ ๋‹ค๋ฅธ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ์— ๋Œ€ํ•œ Branch ์ •๋ณด ํฌํ•จ)

  • Root Node: ํŠธ๋ฆฌ ๋งจ ์œ„์— ์žˆ๋Š” ๋…ธ๋“œ

  • Level: ์ตœ์ƒ์œ„ ๋…ธ๋“œ๋ฅผ Level 0์œผ๋กœ ํ•˜์˜€์„ ๋•Œ, ํ•˜์œ„ Branch๋กœ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ์˜ ๊นŠ์ด๋ฅผ ๋‚˜ํƒ€๋ƒ„

  • Parent Node: ์–ด๋–ค ๋…ธ๋“œ์˜ ๋‹ค์Œ ๋ ˆ๋ฒจ์— ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ

  • Child Node: ์–ด๋–ค ๋…ธ๋“œ์˜ ์ƒ์œ„ ๋ ˆ๋ฒจ์— ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ

  • Leaf Node (Terminal Node): Child Node๊ฐ€ ํ•˜๋‚˜๋„ ์—†๋Š” ๋…ธ๋“œ

  • Sibling (Brother Node): ๋™์ผํ•œ Parent Node๋ฅผ ๊ฐ€์ง„ ๋…ธ๋“œ

  • Depth: ํŠธ๋ฆฌ์—์„œ Node๊ฐ€ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ Level

๐Ÿ’ก Tree BAJ TIL

11725 1167


  • ๋ฐ์ดํ„ฐ์—์„œ ์ตœ๋Œ€๊ฐ’๊ณผ ์ตœ์†Œ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ๊ธฐ ์œ„ํ•ด ๊ณ ์•ˆ๋œ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ (complete binary tree)

  • ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ: ๋…ธ๋“œ๋ฅผ ์‚ฝ์ž…ํ•  ๋•Œ ์ตœํ•˜๋‹จ ์™ผ์ชฝ ๋…ธ๋“œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ์‚ฝ์ž…ํ•˜๋Š” ํŠธ๋ฆฌ

  • ํž™์€ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•˜๊ธฐ ์œ„ํ•œ ๊ตฌ์กฐ (์ตœ๋Œ€ ํž™, Max Heap) ์™€, ์ตœ์†Œ๊ฐ’์„ ๊ตฌํ•˜๊ธฐ ์œ„ํ•œ ๊ตฌ์กฐ (์ตœ์†Œ ํž™, Min Heap) ๋กœ ๋ถ„๋ฅ˜ํ•  ์ˆ˜ ์žˆ์Œ

  • ํž™์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋‘ ๊ฐ€์ง€ ์กฐ๊ฑด์„ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ

    • ๊ฐ ๋…ธ๋“œ์˜ ๊ฐ’์€ ํ•ด๋‹น ๋…ธ๋“œ์˜ ์ž์‹ ๋…ธ๋“œ๊ฐ€ ๊ฐ€์ง„ ๊ฐ’๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๋‹ค. (์ตœ๋Œ€ ํž™์˜ ๊ฒฝ์šฐ)
    • ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ํ˜•ํƒœ๋ฅผ ๊ฐ€์ง
  • ํž™์€ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ์ด๋ฏ€๋กœ, ์‚ฝ์ž…ํ•  ๋…ธ๋“œ๋Š” ๊ธฐ๋ณธ์ ์œผ๋กœ ์™ผ์ชฝ ์ตœํ•˜๋‹จ๋ถ€ ๋…ธ๋“œ๋ถ€ํ„ฐ ์ฑ„์›Œ์ง€๋Š” ํ˜•ํƒœ๋กœ ์‚ฝ์ž…

โ—ผ ํž™์„ ์‚ฌ์šฉํ•ด์•ผ ํ•˜๋Š” ์ด์œ 

  • ๋ฐฐ์—ด์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๊ณ , ์ตœ๋Œ€๊ฐ’๊ณผ ์ตœ์†Œ๊ฐ’์„ ์ฐพ์œผ๋ ค๋ฉด O(n)์ด ๊ฑธ๋ฆผ
  • ์ด์— ๋ฐ˜ํ•ด, ํž™์— ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๊ณ  ์ตœ๋Œ€๊ฐ’๊ณผ ์ตœ์†Œ๊ฐ’์„ ์ฐพ์œผ๋ฉด O(log) ๊ฑธ๋ฆผ
  • ์šฐ์„ ์ˆœ์œ„ ํ์™€ ๊ฐ™์ด ์ตœ๋Œ€๊ฐ’ ๋˜๋Š” ์ตœ์†Œ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ์•„์•ผ ํ•˜๋Š” ์ž๋ฃŒ ๊ตฌ๋…ธ ๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„๋“ฑ์— ํ™œ์šฉ๋จ

๐Ÿ“Œ ์•Œ๊ณ ๋ฆฌ์ฆ˜

- ์ด์ง„ํƒ์ƒ‰ Binary Search

๋งŒ์•ฝ ์ˆ˜๋งŽ์€ ๋ณ‘๋“ค์ค‘ 70๋ฒˆ์งธ์˜ ์ˆซ์ž๊ฐ€ ์ ํžŒ ๋ณ‘๋šœ๊ป‘์„ ์ฐพ๊ฒŒ ๋œ๋‹ค๋ฉด?

image

  • ์ •๋ ฌ์ด ๋˜์–ด์žˆ๋‹ค๋Š” ์กฐ๊ฑดํ•˜์—์„œ 1/2์”ฉ ๋‚˜์šฐ์–ด ์ค‘๊ฐ„์„ ์ฒดํฌํ•˜๊ณ  ์–ด๋А์ชฝ์— ์žˆ๋Š”์ง€ ํŒ๋‹จํ•ด์•ผ ํ•œ๋‹ค.

  • ์ด์ง„ํƒ์ƒ‰ vs ์ˆœ์ฐจํƒ์ƒ‰ => ์ด์ง„ํƒ์ƒ‰ ์†๋„๊ฐ€ ํ›จ์”ฌ ๋น ๋ฅด๋‹ค.

๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์ด์ง„ํƒ์ƒ‰ (Devide and Conquer)

์ฃผ๋กœ ์žฌ๊ท€์šฉ๋ฒ•์„ ๊ฐ€์ง€๊ณ  ๊ตฌํ˜„ํ•œ๋‹ค.
Devide : ๋ฌธ์ œ๋ฅผ ํ•˜๋‚˜ ๋˜๋Š” ๋‘˜ ์ด์ƒ์œผ๋กœ ๋‚˜๋ˆˆ๋‹ค.
Conquer : ๋‚˜๋ˆ ์ง„ ๋ฌธ์ œ๊ฐ€ ์ถฉ๋ถ„ํžˆ ์ž‘๊ณ , ํ•ด๊ฒฐ์ด ๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด ํ•ด๊ฒฐํ•˜๊ณ  ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด ๋‹ค์‹œ ๋‚˜๋ˆˆ๋‹ค.

์ด์ง„ ํƒ์ƒ‰ Devide , Conquer

๋ฆฌ์ŠคํŠธ๋ฅผ 2๊ฐœ์˜ ์Šค๋ธŒ ๋ฆฌ์ŠคํŠธ๋กœ ๋‚˜๋ˆˆ๋‹ค.
๊ฒ€์ƒ‰ํ•  ์ˆซ์ž(search) > ์ค‘๊ฐ„๊ฐ’์ด๋ฉด, ๋’ท๋ถ€๋ถ„์˜ ์„œ๋ธŒ๋ฆฌ์ŠคํŠธ์—์„œ ๊ฒ€์ƒ‰ํ•  ์ˆซ์ž ์ฐพ๊ธฐ
๊ฒ€์ƒ‰ํ•  ์ˆซ์ž(search) < ์ค‘๊ฐ„๊ฐ’ ์ด๋ฉด, ์•ž๋ถ€๋ถ„์˜ ์„œ๋ธŒ ๋ฆฌ์ŠคํŠธ์—์„œ ๊ฒ€์ƒ‰ํ•  ์ˆซ์ž๋ฅผ ์ฐพ๊ธฐ

์ˆœ์ฐจํƒ์ƒ‰ Sequential Search

์—ฌ๋Ÿฌ ๋ฐ์ดํ„ฐ ์ค‘์—์„œ ์›ํ•˜๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ์•„๋‚ด๋Š” ๊ฒƒ์„ ์˜๋ฏธ
๋ฐ์ดํ„ฐ๊ฐ€ ๋‹ด๊ฒจ์žˆ๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ์•ž์—์„œ ๋ถ€ํ„ฐ ํ•˜๋‚˜์”ฉ ๋น„๊ตํ•ด์„œ ์šฐ๋„ˆํ•˜๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ๋Š” ๋ฐฉ๋ฒ•

About

๐Ÿ”ฅ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๐Ÿ”ฅ

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

0