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

์‚ฝ์ž…์ •๋ ฌ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/๊ธฐ๋ณธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ 2022. 1. 10. ์ •๋ ฌ ์ฝ”๋“œ1(๊ณ„์ˆ˜ ์ •๋ ฌ, ์‚ฝ์ž… ์ •๋ ฌ, ์„ ํƒ ์ •๋ ฌ) ๊ณ„์ˆ˜ ์ •๋ ฌ (count sort) ๊ณ„์ˆ˜์ •๋ ฌ์€ ๋ฐ์ดํ„ฐ์˜ ํฌ๊ธฐ ๋ฒ”์œ„๊ฐ€ ์ œํ•œ๋˜์–ด ์ •์ˆ˜ํ˜•ํƒœ๋กœ ํ‘œํ˜„๋  ์ˆ˜ ์žˆ์„๋•Œ ํšจ๊ณผ์ ์œผ๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค. (์ผ๋ฐ˜์ ์œผ๋กœ ํฐ ๋ฐ์ดํ„ฐ์™€ ์ž‘์€ ๋ฐ์ดํ„ฐ์˜ ์ฐจ์ด๊ฐ€ 1,000,000์ด ๋„˜์ง€ ์•Š์„๋•Œ ์‚ฌ์šฉํ•œ๋‹ค.) ๋ฐ์ดํ„ฐ์˜ ๊ฐœ์ˆ˜๊ฐ€ N, ๋ฐ์ดํ„ฐ ์ค‘ ์ตœ๋Œ€๊ฐ’์ด K์ผ๋•Œ, ์ตœ์•…์˜ ๊ฒฝ์šฐ์—๋„ O(n+k)์˜ ์ˆ˜ํ–‰์‹œ๊ฐ„์„ ๋ณด์žฅํ•˜๋Š” ๋น ๋ฅธ ์ •๋ ฌ๋ฒ•์ด๋‹ค. ๋™์ž‘์›๋ฆฌ๋Š” ๋งŒ์•ฝ ์ตœ์†Œ0๋ถ€ํ„ฐ ์ตœ๋Œ€1,000,000์˜ ๋ฐ์ดํ„ฐ๊ฐ€ ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ, '๋ชจ๋“  ๋ฒ”์œ„๋ฅผ ๋‹ด์„ ์ˆ˜ ์žˆ๋Š” ๋ฆฌ์ŠคํŠธ' - ์ฆ‰ 1,000,001๊ฐœ์˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ์„ ์–ธํ•˜์—ฌ ๊ฐ ๊ฐ’์„ ๋‹ด๋Š”๊ฒƒ์ด๋‹ค. ๊ทธ๋ž˜์„œ ๋งค์šฐ ํฐ ๋ฒ”์œ„๋Š” ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค. def count_sort(array): count = [0] * (max(array) + 1) for i in range(len(array)): c..

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”