๋ชฉ๋ก๋ถ„ํ• ์ •๋ณต๋ฒ• (1)

YS's develop story

๋ถ„ํ•  ์ •๋ณต๋ฒ• - Merge Sort, Quick Sort

์•Œ๊ณ ๋ฆฌ์ฆ˜ ) ๋ถ„ํ•  ์ •๋ณต๋ฒ• ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ•ด๊ฒฐ์ „๋žต Divide and Conquer๋ฅผ ๋ถ„ํ•  ์ •๋ณต๋ฒ•์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ถ„ํ•  ์ •๋ณต๋ฒ•์€ ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ์ž‘์€ ์‚ฌ๋ก€๋กœ ๋‚˜๋ˆ„์–ด(Divide) ๊ฐ๊ฐ์˜ ์ž‘์€ ๋ฌธ์ œ๋“ค์„ ํ•ด๊ฒฐ(Conquer)ํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค. ํ”„๋ž‘์Šค์˜ ํ™ฉ์ œ ๋‚˜ํด๋ ˆ์˜น์ด ์ „ํˆฌ์—์„œ ์‚ฌ์šฉํ–ˆ๋˜ ํ›Œ๋ฅญํ•œ ์ „๋žต์—์„œ ์ด๋ฆ„์„ ๋”ฐ์™”๋‹ค๊ณ  ํ•˜๋„ค์š”. ๋‚˜๋ˆ„์–ด๋ผ, ๊ทธ๋ฆฌ๊ณ  ์ •๋ณตํ•˜๋ผ.. ๋ฉ‹์žˆ๋Š” ๋ง์ž…๋‹ˆ๋‹ค... Merge Sort Best Case ์‹œ๊ฐ„๋ณต์žก๋„ : O(n log n) Worst Case ์‹œ๊ฐ„๋ณต์žก๋„ : O(n log n) ๋ถ„ํ•  ๋‹จ๊ณ„ array๋ฅผ ๋‘ ๊ฐœ์˜ subarrays๋กœ ๋‚˜๋ˆ•๋‹ˆ๋‹ค. ์ •๋ณต ๋‹จ๊ณ„ ๊ฐ๊ฐ์˜ subarray๊ฐ€ ์ถฉ๋ถ„ํžˆ ์ž‘๋‹ค๋ฉด ๋ฐ”๋กœ ์ •๋ ฌ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด ์žฌ๊ท€๋ฅผ ํ†ตํ•ด ๊ฐ๊ฐ์„ ์ •๋ ฌํ•ฉ๋‹ˆ๋‹ค. ๊ฒฐํ•ฉ ๋‹จ๊ณ„ ์ •๋ ฌ๋œ๋‘ ๊ฐœ์˜ subarray๋ฅผ ..

Algorithm 2021. 4. 15. 09:40