๐Ÿงฉ ์ž๋ฃŒ๊ตฌ์กฐ/์•Œ๊ณ ๋ฆฌ์ฆ˜

์ฐจ์œ ๋ฆผยท2021๋…„ 11์›” 24์ผ
0

ํŒจ์ŠคํŠธ์บ ํผ์Šค ๋„ค์นด๋ผ์ฟ ๋ฐฐ1๊ธฐ ์ž๋ฃŒ๊ตฌ์กฐ/์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ •๋ฆฌ
https://github.com/ai-creatv/algorithm_nklcb1

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

์ž๋ฃŒ๊ตฌ์กฐ ์ •์˜

  • ์ž๋ฃŒ(Data)
    • ํ˜„์‹ค ์„ธ๊ณ„๋กœ๋ถ€ํ„ฐ ์ˆ˜์ง‘ํ•œ ์‚ฌ์‹ค(์ธก์ •๊ฐ’)์ด๋‚˜ ๊ฐœ๋…์˜ ๊ฐ’ ๋˜๋Š” ์ด๋“ค์˜ ์ง‘ํ•ฉ
    • cf) ์ •๋ณด(Information) : ํŠน์ •์šฉ๋„๋กœ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด ์ฒ˜๋ฆฌ/๊ฐ€๊ณตํ•œ ๊ฒƒ
    • ๊ฐ’์„ ๋ชจ์•„๋†“์€ ๊ฒƒ์ด ์ž๋ฃŒ, ๊ฐ€๊ณตํ•˜๋ฉด ์ •๋ณด!
      ์ •๋ณด์—๋Š” ์‚ฌ๋žŒ์˜ ๊ฐ€์น˜๊ด€์ด ๋“ค์–ด๊ฐ€์žˆ๋‹ค.
      ์˜ˆ๋ฅผ ๋“ค์–ด ํ‰๊ท ์„ ๊ตฌํ• ๋•Œ ์•„์›ƒ๋ผ์ด์–ด๋ฅผ ์ œ์™ธํ•˜๊ธฐ ์œ„ํ•ด ์ƒ/ํ•˜์œ„ 3๋ช…์„ ์ œ์™ธํ•œ๋‹ค๋ฉด,
      ์ด๋Ÿฐ ๊ธฐ์ค€์—๋Š” ๊ฐ€์น˜๊ด€์ด ์ ์šฉ๋œ๋‹ค.
  • ์ž๋ฃŒ๊ตฌ์กฐ(Data Structure)
    • ์ž๋ฃŒ ๊ฐ’์˜ ๋ชจ์ž„, ์ž๋ฃŒ ๊ฐ„์˜ ๊ด€๊ณ„, ์ž๋ฃŒ์— ์ ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ํ•จ์ˆ˜๋‚˜ ๋ช…๋ น์„ ์˜๋ฏธ
    • ex) ๋ถ€์ž์˜ ๋ชจ๊ทผ์ž๋ฃŒ ๋ฐ์ดํ„ฐ ๋ชจ์Œ, ๋ถ€์ž ๊ด€๊ณ„, ์˜ˆ์™ธ ๋ฐ์ดํ„ฐ ์‚ญ์ œ์‹œ ์–ด๋–ป๊ฒŒ ์ฒ˜๋ฆฌํ•  ๊ฒƒ์ธ์ง€ ๋™์ž‘์ด ์žˆ๋Š” ๊ฒƒ.

์ž๋ฃŒ๊ตฌ์กฐ ํŠน์ง•

  • ํšจ์œจ์„ฑ (Efficiency)
    ๋” ์ข‹์€ ์ ์ด ์žˆ๋‹ค.
  • ์ถ”์ƒํ™” (Abstraction)
    ์‚ญ์ œ ๋ช…๋ น์‹œ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•œ๋‹ค๋งŒ ์ถ”์ƒํ™”ํ•˜์—ฌ ๋Œ€ํ™”ํ•˜๊ธฐ ํŽธํ•ด์ง
    ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ•ด์•ผํ•˜๋Š”์ง€ ํ•˜๋‚˜ํ•˜๋‚˜ ๋ช…์‹œํ•˜์ง€ ์•Š์Œ
  • ์žฌ์‚ฌ์šฉ์„ฑ (Reusability)
    = ๋ฒ”์šฉ์ ์œผ๋กœ ์ž‘์„ฑํ•ด์•ผ ํ•œ๋‹ค.
    ํŠน์ •ํ•œ ์ƒํ™ฉ์—๋งŒ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด ์ž๋ฃŒ๊ตฌ์กฐ๋ผ๊ณ  ์ธ์ •๋ฐ›๊ธฐ ์–ด๋ ค์›€.

์ž๋ฃŒ๊ตฌ์กฐ ์ข…๋ฅ˜

  • ์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ
    • ๋ฐฐ์—ด๋ฆฌ์ŠคํŠธ, ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ, ์Šคํƒ, ํ
    • ์ž๋ฃŒ๊ฐ€ ์„ ํ˜•(1์ฐจ)๋กœ ์—ฐ๊ฒฐ๋œ ๊ฒฝ์šฐ
  • ๋น„์„ ํ˜• ์ž๋ฃŒ๊ตฌ์กฐ
    • ํŠธ๋ฆฌ, ๊ทธ๋ž˜ํ”„
    • ์„ ํ˜•์œผ๋กœ ์—ฐ๊ฒฐ๋˜์ง€ ์•Š์€ ๋ชจ๋“  ์ž๋ฃŒ๊ตฌ์กฐ

์ž๋ฃŒ๊ตฌ์กฐ ํ•„์š”์„ฑ

  • ์ž๋ฃŒ๊ตฌ์กฐ์˜ ์„ ํƒ(์ž๋ฃŒ๋ฅผ ์–ด๋–ป๊ฒŒ ์ €์žฅํ• ์ง€)์— ๋”ฐ๋ผ, ํ”„๋กœ๊ทธ๋žจ์— ์˜ํ–ฅ์„ ์ค€๋‹ค.
    • ํ•„์š”ํ•œ ์ž๋ฃŒ์— ํšจ์œจ์ ์œผ๋กœ ๋น ๋ฅด๊ฒŒ ์ ‘๊ทผํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•œ๋‹ค.
    • ์ž๋ฃŒ์˜ ์ค‘๋ณต์„ ์ตœ์†Œํ™”ํ•˜์—ฌ ์ €์žฅ์žฅ์น˜๋ฅผ ํšจ์œจ์ ์œผ๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•œ๋‹ค.
    • ์ž๋ฃŒ๊ตฌ์กฐ๋ณ„๋กœ ์ ์ ˆํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ธฐ๊ณ„์ ์œผ๋กœ ์ ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.
  • ๋‹ค๋งŒ, ๋งŒ๋Šฅ(์ž๋ฃŒ์ ‘๊ทผ์˜ ํšจ์œจ์„ฑ๊ณผ ์ €์žฅ๊ณต๊ฐ„์˜ ํšจ์œจ์„ฑ์„ ๋™์‹œ์— ๋งŒ์กฑ)์ธ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ์—†๋‹ค. ๊ฐ ์ƒํ™ฉ์— ๋”ฐ๋ผ ์ตœ์ ์ธ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ฐพ์•„์„œ ์ ์šฉํ•ด์•ผ ํ•œ๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€?

์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ •์˜

  • ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ์—ฌ๋Ÿฌ ๋™์ž‘๋“ค์˜ ๋ชจ์ž„
  • cf) ๋ฌธ์ œ๋ฅผ ๋” ์‰ฝ๊ฒŒ ๋งŒ๋“ค๊ฑฐ๋‚˜, ๋‹ต์— ๊ทผ์‚ฌํ•œ ๊ฐ’์„ ์–ป๋Š” ๊ฒƒ์€ method

์•Œ๊ณ ๋ฆฌ์ฆ˜ ์กฐ๊ฑด

  • ์ž…๋ ฅ (Input)
    ์™ธ๋ถ€์—์„œ ์ œ๊ณต๋˜๋Š” ์ž๋ฃŒ๊ฐ€ ์กด์žฌํ•œ๋‹ค.
    ์ž…๋ ฅ์ด ์—†๋‹ค๋ฉด ์ถœ๋ ฅ๋„ ์ •ํ•ด์ ธ ์žˆ๋Š” ๊ฒƒ.
  • ์ถœ๋ ฅ (output)
    ์ ์–ด๋„ 2๊ฐ€์ง€ ์ด์ƒ์˜ ๋‹ค๋ฅธ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค.
    ํ•ญ์ƒ ๋˜‘๊ฐ™์€ ๊ฐ’์„ ์ถœ๋ ฅํ•˜๋ฉด ์•ˆ๋œ๋‹ค.
  • ๋ช…ํ™•์„ฑ (Definiteness)
    ์ˆ˜ํ–‰๊ณผ์ •์€ ๋ช…ํ™•ํ•œ ๋ช…๋ น์–ด๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ์–ด์•ผ ํ•œ๋‹ค.(์ฝ”๋“œ๋กœ ์ž‘์„ฑํ•  ์ˆ˜ ์žˆ์„๋งŒํผ)
    โ†” ์ž๋ฃŒ๊ตฌ์กฐ ์ถ”์ƒํ™”
  • ์œ ํ•œ์„ฑ (Finiteness)
    ์œ ํ•œํ•œ ์‹œ๊ฐ„์•ˆ์— ์ข…๋ฃŒ๋˜์–ด์•ผ ํ•œ๋‹ค.
    ์ถœ๋ ฅํ•˜๋Š”๋ฐ ๋ฌดํ•œํ•œ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ๋ฉด ์•ˆ๋จ
  • ํšจ๊ณผ์„ฑ (Effectiveness)
    ๋ฐ์ดํ„ฐ ์ ์„ ๊ฒฝ์šฐ, ์†์œผ๋กœ ์จ๊ฐ€๋ฉด์„œ ๋”ฐ๋ผํ•  ์ˆ˜ ์žˆ์„ ์ •๋„๋กœ
    ๋‹จ์ˆœ/๋ช…๋ฃŒ/๋ช…๋ฐฑ ํ•ด์•ผํ•œ๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ•„์š”์„ฑ

  • ์„œ๋น„์Šค์˜ ๊ทœ๋ชจ๊ฐ€ ์ปค์ ธ๋„, ๋™์ผํ•œ ํผํฌ๋จผ์Šค๋ฅผ ๋‚ด๊ธฐ์œ„ํ•ด
    ์‹ญ๋งŒ๋ช…๊ณผ ๋ฐฑ๋งŒ๊ฑด ์•„์ดํ…œ ์‚ฌ์ด์˜ ๊ด€๊ณ„๋ฅผ ๋‹ค๋ฃจ๋ ค๋ฉด
    100,000 * 1,000,000 = 100,000,000,000๊ฐœ(์ฒœ์–ต, 100๊ธฐ๊ฐ€)์˜ ๊ด€๊ณ„๋ฅผ ๋‹ค๋ค„์•ผํ•จ
    naiveํ•œ ๋ฐฉ์‹์œผ๋กœ๋Š” ์ด๋Ÿฌํ•œ ๋ฐ์ดํ„ฐ๋ฅผ ์‹ค์‹œ๊ฐ„์œผ๋กœ ๋‹ค๋ฃฐ ์ˆ˜ ์—†๋‹ค.
  • ์ปดํ“จํ„ฐ ์—ฐ์‚ฐ ์†๋„์™€ ๋น„์šฉ
    ์—ฐ์‚ฐ์€ ๋น„์šฉ์ด๋‹ค! ๋” ์ข‹์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ์—ฐ์‚ฐ ์†๋„๋ฅผ ๊ฐœ์„ ํ•  ๊ฒฝ์šฐ,
    ๋” ๋‚ฎ์€ ์„œ๋ฒ„ spec์œผ๋กœ๋„ ๋™์ผํ•œ ์„œ๋น„์Šค ์ œ๊ณต ๊ฐ€๋Šฅํ•˜๊ณ 
    ๋” ์งง์€ ์‹œ๊ฐ„ ์„œ๋ฒ„๋ฅผ ์ž„๋Œ€ํ•  ์ˆ˜ ์žˆ๋‹ค.
    (ํด๋ผ์šฐ๋“œ ์„œ๋ฒ„์˜ ๋น„์šฉ์€ ์‹ค์ œ๋กœ ์ž„๋Œ€ํ•œ ์„œ๋ฒ„์˜ spec๊ณผ ์‹œ๊ฐ„์— ๋น„๋ก€ํ•œ๋‹ค)
profile
๐ŸŽจํ”„๋ก ํŠธ์—”๋“œ ๊ฐœ๋ฐœ์ž๐Ÿ’ป

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