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

์ „์ฒด ๊ธ€92

๋ฐฑ์ค€ ์•Œ๊ณ ๋ฆฌ์ฆ˜(BOJ)_1253๋ฒˆ['์ข‹์€ ์ˆ˜' ๊ตฌํ•˜๊ธฐ] '์ข‹์€ ์ˆ˜' ๊ตฌํ•˜๊ธฐ[1253๋ฒˆ] Q. N๊ฐœ์˜ ์ˆ˜ ์ค‘์—์„œ ์–ด๋–ค ์ˆ˜๊ฐ€ ๋‹ค๋ฅธ ์ˆ˜ ๋‘ ๊ฐœ์˜ ํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค๋ฉด ๊ทธ ์ˆ˜๋ฅผ “์ข‹๋‹ค(GOOD)”๊ณ  ํ•œ๋‹ค. N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ๊ทธ ์ค‘์—์„œ ์ข‹์€ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋Š” ๋ช‡ ๊ฐœ์ธ์ง€ ์ถœ๋ ฅํ•˜๋ผ. ์ˆ˜์˜ ์œ„์น˜๊ฐ€ ๋‹ค๋ฅด๋ฉด ๊ฐ’์ด ๊ฐ™์•„๋„ ๋‹ค๋ฅธ ์ˆ˜์ด๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 2,000), ๋‘ ๋ฒˆ์งธ ์ค„์—๋Š” i๋ฒˆ์งธ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” Ai๊ฐ€ N๊ฐœ ์ฃผ์–ด์ง„๋‹ค. (|Ai| ≤ 1,000,000,000, Ai๋Š” ์ •์ˆ˜) ์ถœ๋ ฅ ์ข‹์€ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ์ฒซ ๋ฒˆ์งธ ์ค„์— ์ถœ๋ ฅํ•œ๋‹ค. ๋ฌธ์ œ ๋ถ„์„ N์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ตœ๋Œ€ 2,000์ด๋ผ ๊ฐ€์ •ํ•ด๋„ ์ข‹์€ ์ˆ˜ ํ•˜๋‚˜๋ฅผ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” N2๋ณด๋‹ค ์ž‘์•„์•ผ ํ•จ ์ข‹์€ ์ˆ˜ ํ•˜๋‚˜๋ฅผ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ์ตœ์†Œ O(nlogn)์ด์–ด์•ผ ํ•จ ์ •๋ ฌ๋œ ๋ฆฌ์ŠคํŠธ๋ฅผ ํˆฌ ํฌ์ธํ„ฐ .. 2022. 11. 18.
๋ฐฑ์ค€ ์•Œ๊ณ ๋ฆฌ์ฆ˜(BOJ)_1546๋ฒˆ[ํ‰๊ท  ๊ตฌํ•˜๊ธฐ] ํ‰๊ท  ๊ตฌํ•˜๊ธฐ[1546๋ฒˆ] Q. ์„ธ์ค€์ด๋Š” ๊ธฐ๋ง๊ณ ์‚ฌ๋ฅผ ๋ง์ณค๋‹ค. ์„ธ์ค€์ด๋Š” ์ ์ˆ˜๋ฅผ ์กฐ์ž‘ํ•ด์„œ ์ง‘์— ๊ฐ€์ ธ๊ฐ€๊ธฐ๋กœ ํ–ˆ๋‹ค. ์ผ๋‹จ ์„ธ์ค€์ด๋Š” ์ž๊ธฐ ์ ์ˆ˜ ์ค‘์— ์ตœ๋Œ“๊ฐ’์„ ๊ณจ๋ž๋‹ค. ์ด ๊ฐ’์„ M์ด๋ผ๊ณ  ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‚˜์„œ ๋ชจ๋“  ์ ์ˆ˜๋ฅผ ์ ์ˆ˜/M*100์œผ๋กœ ๊ณ ์ณค๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์„ธ์ค€์ด์˜ ์ตœ๊ณ ์ ์ด 70์ด๊ณ , ์ˆ˜ํ•™์ ์ˆ˜๊ฐ€ 50์ด์—ˆ์œผ๋ฉด ์ˆ˜ํ•™์ ์ˆ˜๋Š” 50/70*100์ด ๋˜์–ด 71.43์ ์ด ๋œ๋‹ค. ์„ธ์ค€์ด์˜ ์„ฑ์ ์„ ์œ„์˜ ๋ฐฉ๋ฒ•๋Œ€๋กœ ์ƒˆ๋กœ ๊ณ„์‚ฐํ–ˆ์„ ๋•Œ, ์ƒˆ๋กœ์šด ํ‰๊ท ์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์‹œํ—˜ ๋ณธ ๊ณผ๋ชฉ์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. ์ด ๊ฐ’์€ 1000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค. ๋‘˜์งธ ์ค„์— ์„ธ์ค€์ด์˜ ํ˜„์žฌ ์„ฑ์ ์ด ์ฃผ์–ด์ง„๋‹ค. ์ด ๊ฐ’์€ 100๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜์ด๊ณ , ์ ์–ด๋„ ํ•˜๋‚˜์˜ ๊ฐ’์€ 0๋ณด๋‹ค ํฌ๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ƒˆ๋กœ์šด ํ‰๊ท ์„ ์ถœ๋ ฅํ•œ๋‹ค. .. 2022. 11. 18.
๋ฐฑ์ค€ ์•Œ๊ณ ๋ฆฌ์ฆ˜(BOJ)_11720๋ฒˆ[์ˆซ์ž์˜ ํ•ฉ ๊ตฌํ•˜๊ธฐ] ์ˆซ์ž์˜ ํ•ฉ ๊ตฌํ•˜๊ธฐ[11720๋ฒˆ] Q. N๊ฐœ์˜ ์ˆซ์ž๊ฐ€ ๊ณต๋ฐฑ ์—†์ด ์จ ์žˆ๋‹ค. ์ด ์ˆซ์ž๋ฅผ ๋ชจ๋‘ ํ•ฉํ•ด ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค ์ž…๋ ฅ 1๋ฒˆ์งธ ์ค„์— ์ˆซ์ž์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 100), 2๋ฒˆ์งธ ์ค„์— ์ˆซ์ž N๊ฐœ๊ฐ€ ๊ณต๋ฐฑ ์—†์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ์ˆซ์ž N๊ฐœ์˜ ํ•ฉ์„ ์ถœ๋ ฅํ•œ๋‹ค. ๋ฌธ์ œ ๋ถ„์„ ์ฐจ๋ก€๋Œ€๋กœ ์ž…๋ ฅ๋ฐ›์€ N๊ฐœ์˜ ์ˆซ์ž๋ฅผ ์ธ๋ฑ์Šค๋ฅผ ์ด์šฉํ•˜์—ฌ ๋”ํ•ด ๋‚˜๊ฐ€๋Š” ๋ฌธ์ œ ์Šˆ๋„์ฝ”๋“œ ์ž‘์„ฑ 1. N๊ฐœ์˜ ๊ฐ’ ์ž…๋ ฅ๋ฐ›๊ธฐ 2. numbers ๋ฆฌ์ŠคํŠธ์— ์ •์ˆ˜ ๊ฐ’ ํ•˜๋‹ˆ์”ฉ ์ž…๋ ฅํ•˜๊ธฐ(๊ณต๋ฐฑ ์—†์ด) 3. sum ๋ณ€์ˆ˜ ์„ ์–ธ 4. for numbers in N: numbers๋ฆฌ์ŠคํŠธ ์ˆœ์ฐจ์ ์œผ๋กœ ํƒ์ƒ‰ sum+=numbers[i] ์ธ๋ฑ์Šค๋ฅผ ์ด์šฉํ•˜์—ฌ ๋”ํ•ด ๋‚˜๊ฐ€๊ธฐ 5. print(sum) sum์ถœ๋ ฅํ•˜๊ธฐ ์ฝ”๋“œ ๊ตฌํ˜„ N=int(input()) #์ˆซ์ž์˜ ๊ฐœ์ˆ˜ .. 2022. 11. 18.
๋ฐฐ์—ด๊ณผ ๋ฆฌ์ŠคํŠธ ๋ฐฐ์—ด : ๋ฉ”๋ชจ๋ฆฌ์˜ ์—ฐ์† ๊ณต๊ฐ„์— ๊ฐ’์ด ์ฑ„์›Œ์ ธ ์žˆ๋Š” ํ˜•ํƒœ์˜ ์ž๋ฃŒ๊ตฌ์กฐ [๋ฐฐ์—ด์˜ ํŠน์ง•] ๋ฐฐ์—ด์˜ ๊ฐ’์€ ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•ด ์ฐธ์กฐ ์„ ์–ธํ•œ ์ž๋ฃŒํ˜•์˜ ๊ฐ’๋งŒ ์ €์žฅ ๊ฐ€๋Šฅ ์ƒˆ๋กœ์šด ๊ฐ’์„ ์‚ฝ์ž…ํ•˜๊ฑฐ๋‚˜ ํŠน์ • ์ธ๋ฑ์Šค์— ์žˆ๋Š” ๊ฐ’ ์‚ญ์ œ ์–ด๋ ค์›€ → ๊ฐ’์„ ์‚ฝ์ž…ํ•˜๊ฑฐ๋‚˜ ์‚ญ์ œํ•˜๋ ค๋ฉด ํ•ด๋‹น ์ธ๋ฑ์Šค ์ฃผ๋ณ€์— ์žˆ๋Š” ๊ฐ’ ์ด๋™์‹œํ‚ค๋Š” ๊ณผ์ • ํ•„์š” ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๋Š” ์„ ์–ธํ•  ๋•Œ ์ง€์ • ๊ฐ€๋Šฅ, ํ•œ ๋ฒˆ ์„ ์–ธํ•˜๋ฉด ํฌ๊ธฐ๋ฅผ ๋Š˜๋ฆฌ๊ฑฐ๋‚˜ ์ค„์ผ ์ˆ˜ ์—†์Œ ๊ตฌ์กฐ๊ฐ€ ๊ฐ„๋‹จ ๋ฆฌ์ŠคํŠธ : ๊ฐ’๊ณผ ํฌ์ธํ„ฐ๋ฅผ ๋ฌถ์€ ๋…ธ๋“œ๋ผ๋Š” ๊ฒƒ์„ ํฌ์ธํ„ฐ๋กœ ์—ฐ๊ฒฐํ•œ ์ž๋ฃŒ๊ตฌ์กฐ [๋ฆฌ์ŠคํŠธ์˜ ํŠน์ง•] ์ธ๋ฑ์Šค๊ฐ€ ์—†์œผ๋ฏ€๋กœ ๊ฐ’์— ์ ‘๊ทผํ•˜๋ ค๋ฉด Headํฌ์ธํ„ฐ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ์ ‘๊ทผํ•ด์•ผํ•จ → ๊ฐ’์— ์ ‘๊ทผํ•˜๋Š” ์†๋„๊ฐ€ ๋А๋ฆผ ํฌ์ธํ„ฐ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์œผ๋ฏ€๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ์‚ฝ์ž…ํ•˜๊ฑฐ๋‚˜ ์‚ญ์ œํ•˜๋Š” ์—ฐ์‚ฐ ์†๋„๊ฐ€ ๋น ๋ฆ„ ์„ ์–ธํ•  ๋•Œ ํฌ๊ธฐ๋ฅผ ๋ณ„๋„๋กœ ์ง€์ •ํ•˜์ง€ ์•Š์•„๋„ ๋จ → ๋ฆฌ์ŠคํŠธ์˜ ํฌ๊ธฐ๋Š” ์ •ํ•ด.. 2022. 11. 18.