์‹œ๊ฐ„ ๋ณต์žก๋„ (Time Complexity), ๊ทธ๋ฆฌ๊ณ  ๊ณต๊ฐ„ ๋ณต์žก๋„ (Space Complexity)

์ž๋ฃŒ ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋ญ”์ง€๋Š” ๋‹ค ์•Œ๊ณ  ์˜ค์…จ์ฃ  ?! ๋ชจ๋ฅด๊ฒ ๋‹ค๊ณ ์š” ..?? ์ œ๊ฐ€ ์„ค๋ช… ์ž˜ ํ•ด๋’€์œผ๋‹ˆ ํ•œ ๋ฒˆ ๋ณด๊ณ  ์˜ค์‹œ์ฃ ! (๋ธ”๋กœ๊ทธ ํ™๋ณด ๐Ÿ˜Ž) ์ž๋ฃŒ๊ตฌ์กฐ, ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ณธ๋ก ์œผ๋กœ ๋Œ์•„์™€์„œ ! ์ž๋ฃŒ ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋ญ”์ง€๋Š” ์ด์ œ ์•Œ์•˜์œผ๋‹ˆ ์šฐ๋ฆฌ๋Š” ์–ด๋–ค ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋น ๋ฅด๊ณ  ํšจ์œจ์ ์ธ์ง€๋ฅผ ํŒ๋‹จํ•  ์ˆ˜ ์žˆ๋Š” ๋Šฅ๋ ฅ์„ ๊ธธ๋Ÿฌ์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๊ธฐ ์œ„ํ•ด์„œ๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„์™€ ๊ณต๊ฐ„ ๋ณต์žก๋„์— ๋Œ€ํ•ด ๋จผ์ € ์•Œ์•„์•ผ ํ•ด์š”. ๊ทธ๋Ÿฐ๋ฐ ์ž ๊น ! ์œ„์— ๊ฐœ๋…์„ ๋ฐฐ์šฐ๊ธฐ ์ „, ํ•œ ๊ฐ€์ง€ ์ƒ๊ฐํ•ด ๋ด์•ผ ํ•  ๊ฒƒ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์šฐ๋ฆฌ๋Š” ์™œ ๋น ๋ฅด๊ณ  ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ฐพ์•„์•ผ ํ• ๊นŒ์š”? ๊ทธ๊ฑด ๋ฐ”๋กœ ์šฐ๋ฆฌ์—๊ฒŒ ์ฃผ์–ด์ง„ ์ž์›์€ ํ•œ์ •๋˜์–ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ˆ˜ํ•™ ๋ฌธ์ œ๋ฅผ ํ‘ผ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ด…์‹œ๋‹ค. ๋ˆ„๊ตฌ๋Š” ๋น ๋ฅด๊ณ  ํšจ์œจ์ ์ธ ํ’€์ด ๋ฐฉ์‹(๊ณต์‹)์œผ๋กœ ๋‹จ ์‹œ๊ฐ„์— ๋ฌธ์ œ๋ฅผ ํ’€ ๊ฒƒ์ด๊ณ , ๋‹ค๋ฅธ ๋ˆ„๊ตฐ๊ฐ€๋Š” ๊ณ„์‚ฐ..

Computer/Algorithm 2024. 1. 18. 15:56