๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•

Dynamic Programming4

[Swift] 2022 KAKAO TECH INTERNSHIP ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๊ณต๋ถ€ Problem ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”. programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์œผ๋กœ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. 1. ์•Œ๊ณ ๋ ฅ๊ณผ ์ฝ”๋”ฉ๋ ฅ์˜ ์ตœ๋Œ€์น˜๋ฅผ ๊ตฌํ•ด์ค€๋‹ค. ๋ฌธ์ œ๋ฅผ ๋ชจ๋‘ ํ’€ ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์€ ์•Œ๊ณ ๋ ฅ๊ณผ ์ฝ”๋”ฉ๋ ฅ์˜ ์ตœ๋Œ€์น˜๋ฅผ ์–ป๋Š” ๋‹ค๋Š” ๊ฒƒ์ด๋ฏ€๋กœ ๋ฏธ๋ฆฌ ๊ตฌํ•ด์ค€๋‹ค. var maxAlp: Int = alp var maxCop: Int = cop problems.forEach { maxAlp = max(maxAlp,$0[0]) maxCop = max(maxCop,$0[1]) } 2. dp ๋ฐฐ์—ด์„ ์•Œ๊ณ ๋ ฅ + 1 , ์ฝ”๋”ฉ๋ ฅ + 1๊ฐœ์˜ ์ด์ค‘ ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด .. 2022. 8. 26.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์˜ฌ๋ฐ”๋ฅธ ๊ด„ํ˜ธ์˜ ๊ฐฏ์ˆ˜ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์˜ฌ๋ฐ”๋ฅธ ๊ด„ํ˜ธ์˜ ๊ฐฏ์ˆ˜ ์˜ฌ๋ฐ”๋ฅธ ๊ด„ํ˜ธ๋ž€ (())๋‚˜ ()์™€ ๊ฐ™์ด ์˜ฌ๋ฐ”๋ฅด๊ฒŒ ๋ชจ๋‘ ๋‹ซํžŒ ๊ด„ํ˜ธ๋ฅผ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. )(๋‚˜ ())() ์™€ ๊ฐ™์€ ๊ด„ํ˜ธ๋Š” ์˜ฌ๋ฐ”๋ฅด์ง€ ์•Š์€ ๊ด„ํ˜ธ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. ๊ด„ํ˜ธ ์Œ์˜ ๊ฐœ์ˆ˜ n์ด ์ฃผ์–ด์งˆ ๋•Œ, n๊ฐœ์˜ ๊ด„ํ˜ธ ์Œ์œผ๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๋ชจ programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์„ ์ด์šฉํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์œผ๋กœ ๊ด„ํ˜ธ๊ฐ€ 1์Œ์ธ ๊ฒƒ๋ถ€ํ„ฐ ์ฃผ์–ด์ง„ n์Œ๊นŒ์ง€ ์ฐจ๊ทผ ์ฐจ๊ทผ ํ’€์–ด๋‚˜๊ฐ€์•ผ ํ•˜๋Š”๋ฐ์š”. ์ง์ ‘ ๊ตฌํ•ด๋ณด๊ธฐ ๊ด„ํ˜ธ๊ฐ€ 1์Œ์ผ ๋• ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ -> ()๋งŒ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค. ๊ด„ํ˜ธ๊ฐ€ 2์Œ์ผ ๊ฒฝ์šฐ -> ()(),(()) ์ด๋ ‡๊ฒŒ ๋‘ ๊ฐœ๊ฐ€ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค. ๊ด„ํ˜ธ๊ฐ€ 3์Œ์ผ ๊ฒฝ์šฐ -> ((())), (()()), (())(), ()(()),()()() ์ด๋ ‡๊ฒŒ 5.. 2022. 3. 6.
[Algorithm] ๋™์  ๊ณ„ํš๋ฒ•(Dynamic Programming)์ด๋ž€? ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ๊ทธ ๋™์•ˆ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ ๋™์  ๊ณ„ํš๋ฒ• ๊ด€๋ จ๋œ ๋ฌธ์ œ๊ฐ€ ๋‚˜์˜ค๋ฉด ์–ด๋ ค์›€์„ ๊ฒช๊ณค ํ–ˆ๋Š”๋ฐ์š”.. ์˜ค๋Š˜์€ ๋™์  ๊ณ„ํš๋ฒ•์— ๋Œ€ํ•ด์„œ ์ œ๋Œ€๋กœ ์ •๋ฆฌ๋ฅผ ํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”! ๋™์  ๊ณ„ํš๋ฒ•(Dynamic Programming)์ด๋ž€? ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์€ 1950๋…„๋Œ€ ๋ฏธ๊ตญ์˜ ์ˆ˜ํ•™์ž์ธ ๋ฆฌ์ฒ˜๋“œ ๋ฒจ๋งจ์ด ์ตœ์ ํ™” ๋ฌธ์ œ(Optimization Problem)๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด์„œ ๊ณ ์•ˆ๋˜์—ˆ๋‹ค. ๋ณต์žกํ•œ ๋ฌธ์ œ๋ฅผ ๊ฐ„๋‹จํ•œ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ํ‘ธ๋Š” ๋ฐฉ๋ฒ•์„ ๋งํ•˜๋ฉฐ ์ด๊ฒƒ์€ ๋ถ€๋ถ„ ๋ฌธ์ œ ๋ฐ˜๋ณต๊ณผ ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ผ๋ฐ˜์ ์ธ ๋ฐฉ๋ฒ•์— ๋น„ํ•ด ๋”์šฑ ์ ์€ ์‹œ๊ฐ„ ๋‚ด์— ํ’€ ๋•Œ ์‚ฌ์šฉํ•œ๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๊ฐ™์ด ํฐ ๋ฌธ์ œ๋ฅผ ์ž‘๊ฒŒ ์ชผ๊ฐœ์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ด ๋‚˜๊ฐ€๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. ๋‹ค.. 2021. 12. 9.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์Šคํ‹ฐ์ปค ๋ชจ์œผ๊ธฐ(2) Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์Šคํ‹ฐ์ปค ๋ชจ์œผ๊ธฐ(2) N๊ฐœ์˜ ์Šคํ‹ฐ์ปค๊ฐ€ ์›ํ˜•์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹ค์Œ ๊ทธ๋ฆผ์€ N = 8์ธ ๊ฒฝ์šฐ์˜ ์˜ˆ์‹œ์ž…๋‹ˆ๋‹ค. ์›ํ˜•์œผ๋กœ ์—ฐ๊ฒฐ๋œ ์Šคํ‹ฐ์ปค์—์„œ ๋ช‡ ์žฅ์˜ ์Šคํ‹ฐ์ปค๋ฅผ ๋œฏ์–ด๋‚ด์–ด ๋œฏ์–ด๋‚ธ ์Šคํ‹ฐ์ปค์— ์ ํžŒ ์ˆซ์ž์˜ ํ•ฉ์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋„๋ก programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” DP(Dynamic Programming)์œผ๋กœ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. 1. ์Šคํ‹ฐ์ปค์˜ ๊ฐฏ์ˆ˜๊ฐ€ 3๊ฐœ ์ดํ•˜๋ผ๋ฉด ๊ฐ€์žฅ ํฐ ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค. ์Šคํ‹ฐ์ปค์˜ ๊ฐฏ์ˆ˜๊ฐ€ 3๊ฐœ ์ดํ•˜๋ผ๋ฉด ํ•˜๋‚˜๋ฐ–์— ๋—„ ์ˆ˜ ์—†์œผ๋ฏ€๋กœ ๊ฐ€์žฅ ํฐ ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค. if sticker.count < 4 { return sticker.max()!} 2. ์ฒซ ๋ฒˆ์งธ ์Šคํ‹ฐ์ปค๋ฅผ ๋œฏ์–ด๋ƒˆ์„ ๊ฒฝ์šฐ์™€ ๋‘ ๋ฒˆ์งธ ์Šคํ‹ฐ์ปค๋ฅผ ๋œฏ์–ด๋ƒˆ์„ ๊ฒฝ์šฐ์˜ dp๋ฅผ ๋งŒ๋“ค์–ด์ค๋‹ˆ๋‹ค. var dp1:.. 2021. 10. 19.
728x90
๋ฐ˜์‘ํ˜•