Home

0

Quick sort algorithm

ํ€ต ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜ํ€ต ์ •๋ ฌ์€ ํ”ผ๋ฒ—์„ ๊ธฐ์ค€์œผ๋กœ ์ขŒ/์šฐ์— ์ž์‹ ๋ณด๋‹ค ํฐ/์ž‘์€ ๊ฐ’์„ ๋ชฐ๊ณ , ๋ฌธ์ œ๋ฅผ ์กฐ๊ธˆ์”ฉ ๋‚˜๋ˆ ๊ฐ€๋ฉฐ ์ •๋ ฌ์„ ํ•˜๊ฒŒ ๋œ๋‹ค. ์ตœ์•…์˜ ๊ฒฝ์šฐ(ํ•ญ์ƒ ํ”ผ๋ฒ—์ด ๋ชจ๋“  ๊ฐ’ ์ค‘ ๊ฐ€์žฅ ์ž‘์€ ๊ฒฝ์šฐ) O(n^2)๋ฅผ ๊ฐ€์ง€๋Š” ์ƒํ™ฉ์ด ๋‚˜์˜ฌ ์ˆ˜ ์žˆ์ง€๋งŒ, ํ™•๋ฅ ์ ์œผ๋กœ ๊ทธ๋Ÿด ์ผ์€ ์ ๊ธฐ์— ํ‰๊ท ์ ์œผ๋กœ O(NlogN)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

0

Dijkstra Algorithm

๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜Dijkstra algorithm(์ดํ•˜ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜)์€ ์Œ์˜ ๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ทธ๋ž˜ํ”„์—์„œ ํ•œ ๋…ธ๋“œ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ฐ€์žฅ ์งง์€ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘ ํ•˜๋‚˜์ด๋‹ค. ์„ ํ˜•๊ตฌ์กฐ๋กœ ๊ตฌํ˜„๋œ ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ O(N^2)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€์ง€๋งŒ ํž™์„ ์ด์šฉํ•ด ๊ตฌํ˜„ํ•˜๊ฒŒ ๋˜๋ฉด O(NlogN)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค. ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒฝ์šฐ๋Š” ํ˜„์‹ค์—์„œ๋„ ํ”ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋งŽ์ด ์‚ฌ์šฉ๋˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.