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

Algorithm9

[๊ตฌ๋ฆ„ํ†ค ์ฑŒ๋ฆฐ์ง€] 1์ฃผ์ฐจ ํ•™์Šต ์ผ๊ธฐ #2 ๋ฌธ์ œ ์„ค๋ช… ๊ตฌ๋ฆ„ ํ–„๋ฒ„๊ฑฐ๋Š” ๋‹ค์–‘ํ•œ ์žฌ๋ฃŒ๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๋งŒ๋“ค์–ด์„œ ๋ง›์žˆ๊ธฐ๋กœ ์œ ๋ช…ํ•˜๋‹ค. ๊ตฌ๋ฆ„ ํ–„๋ฒ„๊ฑฐ๋Š” ๊ฐœ์˜ ์žฌ๋ฃŒ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์Œ“์•„์„œ ๋งŒ๋“ค๊ณ , ๊ตฌ๋ฆ„ ํ–„๋ฒ„๊ฑฐ์˜ ๋ง›์€ ์‚ฌ์šฉ๋œ ๋ชจ๋“  ์žฌ๋ฃŒ์˜ ๋ง›์˜ ์ •๋„๋ฅผ ๋”ํ•œ ๊ฐ’์ด๋‹ค. ์™„๋ฒฝํ•œ ๊ตฌ๋ฆ„ ํ–„๋ฒ„๊ฑฐ๋ฅผ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋ง›์˜ ์ •๋„๊ฐ€ ๊ฐ€์žฅ ๋†’์€ ์žฌ๋ฃŒ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์œ„๋ž‘ ์•„๋ž˜๋กœ ๊ฐˆ์ˆ˜๋ก ์žฌ๋ฃŒ์˜ ๋ง›์˜ ์ •๋„๊ฐ€ ๊ฐ์†Œํ•˜๊ฑฐ๋‚˜ ๊ฐ™์•„์•ผ ํ•œ๋‹ค. ํ”Œ๋ ˆ์ด์–ด๋Š” N๊ฐœ์˜ ์žฌ๋ฃŒ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์Œ“์•„์„œ ๊ตฌ๋ฆ„ ํ–„๋ฒ„๊ฑฐ๋ฅผ ํ•˜๋‚˜ ๋งŒ๋“ค์—ˆ๋‹ค. i๋ฒˆ์งธ๋กœ ์Œ“์€ ์žฌ๋ฃŒ์˜ ๋ง›์˜ ์ •๋„๊ฐ€ ki๋ผ๊ณ  ํ•  ๋•Œ, ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ๋งŒ๋“  ๊ตฌ๋ฆ„ ํ–„๋ฒ„๊ฑฐ์˜ ๋ง›์„ ๊ตฌํ•ด๋ณด์ž. ๋งŒ์•ฝ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์™„๋ฒฝํ•˜์ง€ ์•Š์€ ๊ตฌ๋ฆ„ ํ–„๋ฒ„๊ฑฐ๋ฅผ ๋งŒ๋“ค์—ˆ๋‹ค๋ฉด 0์„ ์ถœ๋ ฅํ•œ๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๊ตฌ๋ฆ„ ํ–„๋ฒ„๊ฑฐ์— ๋“ค์–ด๊ฐ€๋Š” ์žฌ๋ฃŒ์˜ ๊ฐœ์ˆ˜ N๊ฐœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.(1 > num; arr.push_back(num); } int f.. 2023. 8. 17.
[๊ตฌ๋ฆ„ํ†ค ์ฑŒ๋ฆฐ์ง€] 1์ฃผ์ฐจ ํ•™์Šต ์ผ๊ธฐ #1 ๋ฌธ์ œ ์„ค๋ช… ๋ณดํ†ต์˜ ๊ณ„์‚ฐ๊ธฐ๋Š” ํ•œ ๋ฒˆ์— ํ•˜๋‚˜์˜ ๊ณ„์‚ฐ ๊ฒฐ๊ณผ๋งŒ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋ž˜์„œ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ณ„์‚ฐ ๊ฒฐ๊ณผ๊ฐ€ ํ•„์š”ํ•œ ๊ฒฝ์šฐ์—๋Š” ์ด์ „ ๊ณ„์‚ฐ ๊ฒฐ๊ณผ๋ฅผ ๋”ฐ๋กœ ๊ธฐ๋กํ•ด ๋‘ฌ์•ผ ํ•˜๋Š” ๋ฒˆ๊ฑฐ๋กœ์›€์ด ์žˆ์—ˆ๋‹ค. ํ”Œ๋ ˆ์ด์–ด๋Š” ์ด๋Ÿฌํ•œ ์ ์„ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด์„œ ํ•ฉ ๊ณ„์‚ฐ๊ธฐ๋ฅผ ๋งŒ๋“ค์—ˆ๋‹ค. ํ•ฉ ๊ณ„์‚ฐ๊ธฐ๋Š” ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ณ„์‚ฐ์‹์„ ์ž…๋ ฅ๋ฐ›์€ ๋’ค, ๊ฐ๊ฐ์˜ ๊ณ„์‚ฐ ๊ฒฐ๊ณผ๋ฅผ ๋ชจ๋‘ ํ•ฉํ•ด์„œ ์ถœ๋ ฅํ•˜๋Š” ๊ธฐ๋Šฅ์„ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ํ•ฉ ๊ณ„์‚ฐ๊ธฐ์— ์ž…๋ ฅํ•  ์ˆ˜ ์žˆ๋Š” ๊ณ„์‚ฐ์‹์€ ์•„๋ž˜ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•ด์•ผ ํ•œ๋‹ค. ๊ณ„์‚ฐ์‹์€ ํ˜•ํƒœ์ด๋‹ค. ์—๋Š” ๋”ํ•˜๊ธฐ, ๋นผ๊ธฐ, ๊ณฑํ•˜๊ธฐ, ๋‚˜๋ˆ„๊ธฐ์˜ ๋„ค ๊ฐ€์ง€ ์‚ฌ์น™ ์—ฐ์‚ฐ ๊ธฐํ˜ธ๊ฐ€ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋‹ค. ์ด๋•Œ, ๋‚˜๋ˆ—์…ˆ ๊ฒฐ๊ณผ์˜ ๋‚˜๋จธ์ง€๋Š” ๋ฒ„๋ฆฐ๋‹ค.ํ•ฉ ๊ณ„์‚ฐ๊ธฐ์— ์ž…๋ ฅํ•  ๊ฐœ์˜ ๊ณ„์‚ฐ์‹์ด ์ฃผ์–ด์งˆ ๋•Œ, ํ•ฉ ๊ณ„์‚ฐ๊ธฐ์˜ ์ถœ๋ ฅ ๊ฒฐ๊ณผ๋ฅผ ๊ตฌํ•ด๋ณด์ž. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์‹์˜ ๊ฐœ์ˆ˜ ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ T ๊ฐœ์˜ ์ค„์—๋Š” ๊ณ„์‚ฐ์‹์ด.. 2023. 8. 16.
DP- ๋™์  ๊ณ„ํš๋ฒ• - DP๋ž€?DP๋Š” ํ•˜๋‚˜์˜ ํฐ ๋ฌธ์ œ๋ฅผ ์ž‘์€ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ํ•ด๊ฒฐํ•˜๋Š” ๊ธฐ๋ฒ•์„ ์˜๋ฏธํ•œ๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋ถ„๋ฅ˜๋กœ ๋„ฃ๊ธด ํ–ˆ์œผ๋ฉด ์ด๋Š” ์‚ฌ์‹ค ๋ฐฉ๋ฒ•๋ก ์ด๋ผ๊ณ  ํ•˜๋Š” ๊ฒŒ ๋” ๋งž๋Š” ๊ฒƒ ๊ฐ™๋‹ค. ์ด๋ฆ„์˜ ๋œป์ด ๋ญ”๊ฐ€ ๊นŠ์€ ์˜๋ฏธ๊ฐ€ ๋‹ด๊ฒจ ์žˆ์–ด ๋ณด์ด์ง€๋งŒ, ๊ทธ๋ƒฅ ๋ฉ‹์žˆ์–ด์„œ ์ง€์€ ์ด๋ฆ„์ด๋ฏ€๋กœ ์ด๋ฆ„๊ณผ ํ•ด๋‹น ๋ฐฉ๋ฒ•์— ์—ฐ๊ด€์ด ์žˆ๋‹ค๋Š” ์ƒ๊ฐ์€ ๋ฒ„๋ฆฌ๋Š” ๊ฒƒ์ด ์ข‹๋‹ค.  - ์™œ ์“ฐ๋‚˜์š”?๊ฒฐ๋ก ๋ถ€ํ„ฐ ๋งํ•˜์ž๋ฉด ์ตœ์ ํ™”๋‹ค. ํ›„์— ์„ค๋ช…๋  Momozation ๊ธฐ๋ฒ•์„ ์‚ฌ์šฉํ•˜์—ฌ ์ฒ˜์Œ ๊ฐ’์„ ๋ณด๊ด€ํ•ด๋†“๊ณ  ์ด๋ฅผ ํ™œ์šฉํ•˜๋Š” ๋ฐฉ์‹์ด๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ™์€ ์—ฐ์‚ฐ์„ ์—ฌ๋Ÿฌ ๋ฒˆ ๋ฐ˜๋ณตํ•  ํ•„์š”๊ฐ€ ์—†์–ด ์ตœ์ ํ™”์— ์šฉ์ดํ•˜๋‹ค.  - ์–ธ์ œ ์“ฐ๋‚˜์š”?DP๋ฅผ ์ ์šฉํ•ด๋ณด๊ธฐ ์œ„ํ•ด์„œ๋Š” 2๊ฐ€์ง€ ์กฐ๊ฑด์ด ํ•„์š”ํ•˜๋‹ค.1. ๊ฒน์น˜๋Š” ์†Œ๋ฌธ์ œ์ž‘์€ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์—ˆ์„ ๋•Œ, ์ค‘๋ณต๋˜๋Š” ๋ถ€๋ถ„์ด ์—†์ด ๊ฐ ์†Œ๋ฌธ์ œ์˜ ๊ฒฐ๊ณผ๋ฅผ ํ™œ์šฉํ•  ์ˆ˜ ์—†๋‹ค๋ฉด DP๋ฅผ ์ ์šฉํ•˜๊ธฐ ์–ด๋ ต๋‹ค.2... 2023. 8. 15.