Category: Algorithm

0

๊ธฐ์ดˆ DP์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ

๋ฐฐ๋‚ญ ์•Œ๊ณ ๋ฆฌ์ฆ˜(a.k.a Knapsack problem)๋ฐฐ๋‚ญ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ชผ๊ฐค ์ˆ˜ ์—†๋Š” ๋ฌผ๊ฑด์ด ์ œํ•œ๋œ ๊ฐ€๋ฐฉ์— ์ตœ๋Œ€ํ•œ์˜ ๊ฐ€์น˜๋กœ ๋‹ด๋Š” ๋ฌธ์ œ์ด๋‹ค. Fractional Knapsack ๋ฌธ์ œ๋Š” ํƒ์š• ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ์—ˆ์ง€๋งŒ, ์กฐ๊ฑด์—์„œ ์ชผ๊ฐค ์ˆ˜ ์žˆ์–ด์„œ ๊ฐ€๋Šฅํ–ˆ๋‹ค. ์•ž์„œ ์ชผ๊ฐค ์ˆ˜ ์—†๋Š” ๋ฌผ๊ฑด์„ ์ตœ๋Œ€ํ•œ์˜ ๊ฐ€์น˜๋ฅผ ๊ฐ€์ง€๋ฉฐ ๋‹ด๊ธฐ ์œ„ํ•ด์„œ๋Š” DP๋ฅผ ํ†ตํ•ด์„œ ํ•ด๊ฒฐํ•˜๊ฒŒ ๋œ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜

0

Merge sort algorithm

ํ•ฉ๋ณ‘ ์ •๋ ฌ(merge sort)ํ•ฉ๋ณ‘ ์ •๋ ฌ์€ ๋ถ„ํ• ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ฉฐ ๊ธธ์ด๊ฐ€ N์ธ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ธธ์ด๊ฐ€ 1์ธ ๋ฆฌ์ŠคํŠธ๋กœ ์ชผ๊ฐœ๊ณ  ๋‹ค์‹œ ์ชผ๊ฐœ์ง„ ๊ฐ๊ฐ์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•˜๋ฉฐ ํ•ฉ๋ณ‘ํ•ด ์ตœ์ข…์ ์œผ๋กœ ์ •๋ ฌ๋œ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ฐ€์ง€๊ฒŒ ๋œ๋‹ค. ํ•จ์ˆ˜์˜ ๊ตฌ์กฐ๋ฅผ ๋ณด๋ฉด ์•Œ๊ฒ ์ง€๋งŒ, ์ค‘์•™ ์œ„์น˜๋ฅผ ์ฐพ๊ณ  ์ค‘์•™ ์œ„์น˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ขŒ์ธก, ์šฐ์ธก์„ ๋‚˜๋ˆ  ์žฌ๊ท€ ํ˜ธ์ถœ๋œ๋‹ค. ์žฌ๊ท€ ์ข…๋ฃŒ ์กฐ๊ฑด์€ start < end์˜ ์กฐ๊ฑด์— ๋งž์ง€ ์•Š๋Š”๋‹ค๋ฉด ๋” ๋‚˜๋‰  ์ˆ˜ ์—†๋‹ค๊ณ  ํŒ๋‹จํ•˜์—ฌ ์ชผ๊ฐœ๋Š” ๊ณผ์ •์ด ์ข…๋ฃŒ๋œ๋‹ค. ์ตœ์ข…์ ์œผ๋กœ ๋งˆ์ง€๋ง‰ mergeํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•ด ๊ฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ํ•ฉ๋ณ‘ํ•œ๋‹ค. ์ค‘์š”ํ•œ ์ ์€ ์ด๋•Œ ์ž„์‹œ๋ฒ„ํผ๋ฅผ ์‚ฌ์šฉํ•ด์•ผ ํ•˜๋Š”๋ฐ, ๋งŒ์•ฝ ์ž„์‹œ๋ฒ„ํผ๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋Š” ์กฐ๊ฑด์ด๋ผ๋ฉด ํ•ฉ๋ณ‘ ์ •๋ ฌ์€ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค.

0

Quick sort algorithm

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

0

Dijkstra Algorithm

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