Home > Data Structure > ๐Ÿงฉ [Data Structure] ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์žฌ๊ท€

๐Ÿงฉ [Data Structure] ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์žฌ๊ท€
Data Structure

๐Ÿงฉ [Data Structure] ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์žฌ๊ท€

โœ…1๏ธโƒฃ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์žฌ๊ท€.

๐Ÿ“Œ Intro.

  • โ†˜๏ธŽ ์žฌ๊ท€: โ€˜๋‚ด ์•ˆ์˜ ๋‚˜๋ฅผ ์ฐพ๋Š” ๊ฒƒโ€™
    • โ†˜๏ธŽ ์ฆ‰, ์„ฑ๊ฒฉ์€ ๊ฐ™๊ณ  ํฌ๊ธฐ๋งŒ ์ž‘์€ ๋‚˜๋ฅผ ์ฐพ์•„ ํฐ ๋‚˜์™€ ์ž‘์€ ๋‚˜๊ฐ€ ์—ฐ๊ฒฐ๋œ ๊ด€๊ณ„๋ฅผ ๋“œ๋Ÿฌ๋‚ด๋Š” ๊ฒƒ.

โœ…2๏ธโƒฃ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์žฌ๊ท€์˜ ์˜ˆ์‹œ.

  • โ†˜๏ธŽ ํŒฉํ† ๋ฆฌ์–ผ(Factorial)
    • โ†˜๏ธŽ 1๋ถ€ํ„ฐ n๊นŒ์ง€ ๊ณฑํ•˜๋Š” n!(n ํŒฉํ† ๋ฆฌ์–ผ)์€ $n!\ =\ 1\ ร—\ 2\ ร—\ 3 \ ร— ๏น’๏น’๏น’\ ร— \ (n-1)\ ร—\ n$ ์ด๋‹ค.
    • โ†˜๏ธŽ ์—ฌ๊ธฐ์„œ ๋งจ ๋์— n๋งŒ ์ œ์™ธํ•˜๋ฉด $1\ ร—\ 2\ ร—\ 3 \ ร— ๏น’๏น’๏น’\ ร— \ (n-1)$์ธ๋ฐ ์ด๊ฒƒ์€ (n-1)!์ด๋‹ค.
      • โ†˜๏ธŽ n!์€ ์—ฌ๊ธฐ์— n๋งŒ ๋” ๊ณฑํ•˜๋ฉด ๋œ๋‹ค.
        • โ†˜๏ธŽ โ€œ์ฆ‰, $n!\ =\ n\ ร—\ (n-1)!$โ€
          • โ†˜๏ธŽ ํฌ๊ธฐ๊ฐ€ n์ธ ํŒฉํ† ๋ฆฌ์–ผ์€ ํฌ๊ธฐ๊ฐ€ n-1์ธ ํŒฉํ† ๋ฆฌ์–ผ์„ ํฌํ•จํ•˜๊ณ  ์žˆ๋‹ค.
          • โ†˜๏ธŽ ์ฆ‰, ์„ฑ๊ฒฉ์€ ๊ฐ™๊ณ  ํฌ๊ธฐ๋งŒ ์ž‘์€ ๋‚˜๋ฅผ ์ฐพ์•„ ํฐ ๋‚˜์™€ ์ž‘์€ ๋‚˜๊ฐ€ ์—ฐ๊ฒฐ๋œ ๊ด€๊ณ„๋ฅผ ๋“œ๋Ÿฌ๋‚ธ ๊ฒƒ์ด๋‹ค.
            • โ†˜๏ธŽ ์ด์ฒ˜๋Ÿผ ์–ด๋–ค ๋ฌธ์ œ๋‚˜ ํ•จ์ˆ˜ ๋“ฑ์ด ์ž์‹ ๊ณผ ์„ฑ๊ฒฉ์ด ๋˜‘๊ฐ™์ง€๋งŒ ํฌ๊ธฐ๊ฐ€ ๋” ์ž‘์€ ๋ฌธ์ œ๋ฅผ ํ•˜๋‚˜ ์ด์ƒ ํฌํ•จํ•˜๊ณ  ์žˆ์„ ๋•Œ โ€œ์žฌ๊ท€์  ๊ตฌ์กฐโ€๋ฅผ ๊ฐ–๊ณ  ์žˆ๋‹ค๊ณ  ๋งํ•œ๋‹ค.

โœ…3๏ธโƒฃ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ทธ๋ฆฌ๊ณ  ์žฌ๊ท€์˜ ๊ด€๊ณ„.

  • โ†˜๏ธŽ ๋Œ€๋ถ€๋ถ„์˜ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด๋Š” ํ•จ์ˆ˜ ๋‚ด๋ถ€์—์„œ ์ž์‹ ์„ ํ˜ธ์ถœํ•˜๋Š” ์ž๊ธฐํ˜ธ์ถœ(์žฌ๊ท€) ๊ธฐ๋Šฅ์„ ์ œ๊ณตํ•œ๋‹ค.
    • โ†˜๏ธŽ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ด€๊ณ„ ์ค‘์‹ฌ์˜ ์‚ฌ๊ณ ๋ฐฉ์‹์„ ํ›ˆ๋ จํ•˜๋Š” ๋„๊ตฌ์ด๊ธฐ๋„ ํ•˜๋‹ค.
  • โ†˜๏ธŽ ์žฌ๊ท€๋Š” ํ•™๋ถ€์—์„œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋‹ค๋ฃฐ ๋•Œ ๋ช…์‹œ์ ์œผ๋กœ 40% ์ •๋„, ๋ช…์‹œ์ ์œผ๋กœ ๋“œ๋Ÿฌ๋‚˜์ง€ ์•Š์ง€๋งŒ ์žฌ๊ท€์  ์„ฑ๊ฒฉ์„ ๊ฐ–๊ณ  ์žˆ๋Š” ๊ฒƒ ๊นŒ์ง€ ํ•ฉํ•˜๋ฉด 80% ์ •๋„๋‚˜ ์ฐจ์ง€ํ•˜๋Š” ์ฃผ์ œ๋‹ค.
  • โ†˜๏ธŽ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ๋„ ์ƒ๋‹นํžˆ ๋†’์€ ๋น„์œจ์„ ์ฐจ์ง€ํ•œ๋‹ค.
  • โ†˜๏ธŽ ์žฌ๊ท€๋ฅผ ๋ชจ๋ฅด๊ณ  ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ณต๋ถ€ํ•  ์ˆ˜ ์—†๋‹ค.
  • โ†˜๏ธŽ ์žฌ๊ท€๋Š” ์ปดํ“จํ„ฐ ๊ณผํ•™ ์ด๋ก ์˜ ๊ทผ๊ฐ„์„ ์ด๋ฃจ๋Š” ์ค‘์š” ๊ฐœ๋…์œผ๋กœ, ์–ด๋ ต๊ฑฐ๋‚˜ ํŠน๋ณ„ํ•œ ์ฃผ์ œ๊ฐ€ ์•„๋‹ˆ๋‹ค.
  • โ†˜๏ธŽ ์ปดํ“จํ„ฐ ๊ณผํ•™์„ ๊ณต๋ถ€ํ•˜๋‹ค ๋ณด๋ฉด ์žฌ๊ท€๋Š” ๋Š์ž„์—†์ด ๋‹ค์–‘ํ•œ ์–ผ๊ตด๋กœ ์ถœํ˜„ํ•œ๋‹ค.
    • โ†˜๏ธŽ ๋”ฐ๋ผ์„œ ์ด ์ฃผ์ œ์— ๋Œ€ํ•ด ์ˆจ ์‰ฌ๋“ฏ์ด ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ๋ฐ›์•„๋“ค์—ฌ์•ผ ํ•œ๋‹ค.