๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Algorithm

์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ฐœ์š”

๐Ÿ“š Prologue

์ด ๊ฒŒ์‹œ๋ฌผ์€ ์ €์˜ ์ง€๋‚œ๊ฒŒ์‹œ๋ฌผ(์ž๋ฃŒ๊ตฌ์กฐ)๊ณผ ์ด์–ด์ง‘๋‹ˆ๋‹ค!

์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ ์ €์™€ ํ•จ๊ป˜ ๊ณต๋ถ€ํ•ด์š”๐Ÿฅ•๐Ÿฅ•

 

์ž๋ฃŒ๊ตฌ์กฐ ๊ฐœ์š” ๋ณด๋Ÿฌ๊ฐ€๊ธฐ ๐Ÿ‘‰https://hizzine.tistory.com/6

๐Ÿ”Ž ์•Œ๊ณ ๋ฆฌ์ฆ˜

์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์˜๋ฏธ๋Š” ๋‘๊ฐ€์ง€๋กœ ๋‚˜๋ˆ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

๋„“์€์˜๋ฏธ: ์ž๋ฃŒ๊ตฌ์กฐ์™€ ํ•จ๊ป˜ ์ปดํ“จํ„ฐ ํ”„๋กœ๊ทธ๋žจ์„ ๊ตฌ์„ฑํ•˜๋Š” ํ•œ๊ฐ€์ง€ ์š”์†Œ(์ปดํ“จํ„ฐ ๋ช…๋ น์–ด๋“ค์˜ ์ง‘ํ•ฉ)

์ข์€์˜๋ฏธ: ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ์ผ๋ จ์˜ ๋ฐฉ๋ฒ• ๋˜๋Š” ์ ˆ์ฐจ. ๋ฌธ์ œํ•ด๊ฒฐ๋ฐฉ๋ฒ•์„ ์ˆœ์„œ๋Œ€๋กœ, ์ ˆ์ฐจ๋Œ€๋กœ ๋‚˜์—ดํ•œ ๊ฒƒ

 

๐Ÿ”Ž ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ 5๊ฐ€์ง€ ํŠน์„ฑ

  1. ์ž…๋ ฅ(input): ์™ธ๋ถ€์—์„œ 0๊ฐœ์ด์ƒ์˜ ์ž๋ฃŒ๊ฐ€ ์ž…๋ ฅ๋˜์–ด์•ผ ํ•œ๋‹ค.
  2. ์ถœ๋ ฅ(output): ์ ์–ด๋„ 1๊ฐœ ์ด์ƒ์˜ ๊ฒฐ๊ณผ๋ฅผ ๋งŒ๋“ค์–ด์•ผ ํ•œ๋‹ค.
  3. ๋ช…๋ฐฑ์„ฑ(definiteness): ๊ฐ ๋ช…๋ น์–ด๋Š” ์˜๋ฏธ๊ฐ€ ๋ชจํ˜ธํ•˜์ง€ ์•Š๊ณ  ๋ช…ํ™•ํ•ด์•ผ ํ•œ๋‹ค.
  4. ์œ ํ•œ์„ฑ(finiteness): ํ•œ์ •๋œ ์ˆ˜์˜ ๋‹จ๊ณ„ ๋’ค์—๋Š” ๋ฐ˜๋“œ์‹œ ์ข…๋ฃŒ๋œ๋‹ค. (๋ฌดํ•œํžˆ ๋™์ž‘ํ•ด์„œ๋Š” ์•ˆ ๋œ๋‹ค.)
  5. ์œ ํšจ์„ฑ(effectiveness): ๋ชจ๋“  ๋ช…๋ น์€ ์‹คํ–‰ ๊ฐ€๋Šฅํ•œ ์—ฐ์‚ฐ์ด์–ด์•ผ ํ•œ๋‹ค.

๐Ÿ”Ž ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ๊ด€๊ณ„

์ž๋ฃŒ๊ตฌ์กฐ์˜ ๊ธฐ๋ณธ์ ์ธ ์—ฐ์‚ฐ์„ ๊ตฌํ˜„ํ•˜๊ธฐ ์œ„ํ•ด์„œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์‚ฌ์šฉ๋˜๊ธฐ ๋•Œ๋ฌธ์—,

์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ฑ๋Šฅ์€ ์ž๋ฃŒ๊ตฌ์กฐ์— ์ข…์†๋ฉ๋‹ˆ๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ์ž๋ฃŒ๊ตฌ์กฐ ๊ผญ ๊ฐ™์ด ๊ณต๋ถ€ํ•ด์•ผ๊ฒ ์ฃ !?๐Ÿ™Œ

 

๐Ÿ”Ž ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ‘œํ˜„

  • ์ž์—ฐ์–ด: ์šฐ๋ฆฌ๊ฐ€ ์ผ์ƒ์ƒํ™œ์—์„œ ์‚ฌ์šฉํ•˜๋Š” ์–ธ์–ด๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ธฐ์ˆ ํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.
์žฅ์ : ์‚ฌ์šฉ๊ณผ ๋‚ด์šฉ ์ดํ•ด๊ฐ€ ์‰ฝ๋‹ค.
๋‹จ์ : ๋ช…ํ™•ํ•œ ์˜๋ฏธ์ „๋‹ฌ์ด ํž˜๋“ค๋‹ค.

 

  • ์ˆœ์„œ๋„: ๋ฏธ๋ฆฌ ์ •์˜๋œ ๊ธฐํ˜ธ์™€ ๋„ํ˜•๋“ค์„ ์ด์šฉํ•˜์—ฌ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.

์žฅ์ : ๋„ํ˜•์„ ์‚ฌ์šฉํ•˜๊ณ , ์ง๊ด€์ ์œผ๋กœ ํ‘œํ˜„๋˜์–ด ์ดํ•ดํ•˜๊ธฐ ์‰ฝ๋‹ค.
๋‹จ์ : ๋‚ด์šฉ์ด ๋ณต์žกํ•  ๊ฒฝ์šฐ ํ‘œํ˜„์ด ์–ด๋ ต๊ณ , ์„ธ๋ฐ€ํ•œ ๋ถ€๋ถ„์— ๋Œ€ํ•œ ๋ฌ˜์‚ฌ๊ฐ€ ์–ด๋ ต๋‹ค.
๊ฐ€์žฅ ๋งŽ์ด ์‚ฌ์šฉ๋˜๋Š” ๋ฐฉ๋ฒ• ์ค‘ ํ•˜๋‚˜.

 

  • ์˜์‚ฌ์ฝ”๋“œ: ์ž์—ฐ์–ด๋ฅผ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด์ฒ˜๋Ÿผ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.
์žฅ์ : ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด์— ๋Œ€ํ•œ ์ง€์‹์ด ์—†๋”๋ผ๋„ ์‰ฝ๊ฒŒ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.
๋‹จ์ : ์‚ฌ์šฉํ•˜๋Š” ์‚ฌ๋žŒ์— ๋”ฐ๋ผ ๋‹ค๋ฅธ ๋ฐฉ์‹์œผ๋กœ ์ž‘์„ฑ๋  ์ˆ˜ ์žˆ์–ด ์ดํ•ดํ•˜๊ธฐ ์–ด๋ ค์šธ ์ˆ˜ ์žˆ๋‹ค.
์ˆœ์„œ๋„์™€ ํ•จ๊ป˜ ๋งŽ์ด ์“ฐ์ด๋Š” ๋ฐฉ๋ฒ•์ค‘ ํ•˜๋‚˜.

 

  • ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด: ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.
์žฅ์ : ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ปดํ“จํ„ฐ์—์„œ ๋ฐ”๋กœ ์‹คํ–‰ํ•  ์ˆ˜ ์žˆ๋‹ค.
๋‹จ์ : ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด๋ฅผ ๋ชจ๋ฅธ๋‹ค๋ฉด ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค. ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด์— ๋Œ€ํ•œ ์ดํ•ด๊ฐ€ ํ•„์ˆ˜์ ์ด๋‹ค.

 

๐Ÿ”Ž ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ๋ถ„์„

๋ฌธ์ œ๋ฅผ ๊ฐ€์žฅ ํšจ์œจ์ ์œผ๋กœ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์„ ์ฐพ๊ธฐ ์œ„ํ•ด์„œ ์—ฌ๋Ÿฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ์„ ๋ถ„์„ํ•˜๊ณ  ๋น„๊ตํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ฑ๋Šฅ ํŒ๋‹จ๊ธฐ์ค€์€ ์ •ํ™•์„ฑ, ๋ช…ํ™•์„ฑ, ์ˆ˜ํ–‰๋Ÿ‰, ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์šฉ๋Ÿ‰, ์ตœ์ ์„ฑ ๋“ฑ์ด ์žˆ์Šต๋‹ˆ๋‹ค.

์ด๋Ÿฌํ•œ ๊ธฐ์ค€๋“ค์„ ๋ฐ”ํƒ•์œผ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํฌ๊ฒŒ ๋‘๊ฐ€์ง€ ๋ฐฉ๋ฒ•์œผ๋กœ ๋ถ„์„๋ฉ๋‹ˆ๋‹ค.

 

1. ๊ณต๊ฐ„๋ณต์žก๋„(Space Complexcity)

ํ”„๋กœ๊ทธ๋žจ์œผ๋กœ ์‹คํ–‰๋˜์–ด ์™„๋ฃŒ๋˜๋Š”๋ฐ ๊นŒ์ง€ ํ•„์š”ํ•œ ๋ฉ”๋ชจ๋ฆฌ(์ €์žฅ๊ณต๊ฐ„)์˜ ์‚ฌ์šฉ๋Ÿ‰

 

2. ์‹œ๊ฐ„๋ณต์žก๋„

ํ”„๋กœ๊ทธ๋žจ์œผ๋กœ ์‹คํ–‰๋˜์–ด ์™„๋ฃŒ๋˜๋Š”๋ฐ ๊นŒ์ง€ ์‹ค์ œ๋กœ ๊ฑธ๋ฆฐ ์‹œ๊ฐ„์„ ์ธก์ •
์‚ฌ์šฉํ•œ ๋ช…๋ น๋ฌธ์˜ ๊ฐฏ์ˆ˜๋ฅผ ์ธก์ •

 

๐Ÿ“š Epilogue

๋‹ค์Œ์€ ์‹œ๊ฐ„๋ณต์žก๋„, ๊ณต๊ฐ„๋ณต์žก๋„์— ๋Œ€ํ•œ ์ž์„ธํ•œ ๋‚ด์šฉ๊ณผ ํ‘œ๊ธฐ๋ฒ•์— ๋Œ€ํ•ด ํฌ์ŠคํŒ…ํ•  ์˜ˆ์ •์ž…๋‹ˆ๋‹ค๐Ÿ‘