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

์•Œ๊ณ ๋ฆฌ์ฆ˜49

[Algorithm] ๋™์  ๊ณ„ํš๋ฒ•(Dynamic Programming)์ด๋ž€? ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ๊ทธ ๋™์•ˆ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ ๋™์  ๊ณ„ํš๋ฒ• ๊ด€๋ จ๋œ ๋ฌธ์ œ๊ฐ€ ๋‚˜์˜ค๋ฉด ์–ด๋ ค์›€์„ ๊ฒช๊ณค ํ–ˆ๋Š”๋ฐ์š”.. ์˜ค๋Š˜์€ ๋™์  ๊ณ„ํš๋ฒ•์— ๋Œ€ํ•ด์„œ ์ œ๋Œ€๋กœ ์ •๋ฆฌ๋ฅผ ํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”! ๋™์  ๊ณ„ํš๋ฒ•(Dynamic Programming)์ด๋ž€? ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ์€ 1950๋…„๋Œ€ ๋ฏธ๊ตญ์˜ ์ˆ˜ํ•™์ž์ธ ๋ฆฌ์ฒ˜๋“œ ๋ฒจ๋งจ์ด ์ตœ์ ํ™” ๋ฌธ์ œ(Optimization Problem)๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด์„œ ๊ณ ์•ˆ๋˜์—ˆ๋‹ค. ๋ณต์žกํ•œ ๋ฌธ์ œ๋ฅผ ๊ฐ„๋‹จํ•œ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ํ‘ธ๋Š” ๋ฐฉ๋ฒ•์„ ๋งํ•˜๋ฉฐ ์ด๊ฒƒ์€ ๋ถ€๋ถ„ ๋ฌธ์ œ ๋ฐ˜๋ณต๊ณผ ์ตœ์  ๋ถ€๋ถ„ ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ผ๋ฐ˜์ ์ธ ๋ฐฉ๋ฒ•์— ๋น„ํ•ด ๋”์šฑ ์ ์€ ์‹œ๊ฐ„ ๋‚ด์— ํ’€ ๋•Œ ์‚ฌ์šฉํ•œ๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๊ฐ™์ด ํฐ ๋ฌธ์ œ๋ฅผ ์ž‘๊ฒŒ ์ชผ๊ฐœ์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ด ๋‚˜๊ฐ€๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. ๋‹ค.. 2021. 12. 9.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€ 3 ๊ณต ์ด๋™ ์‹œ๋ฎฌ๋ ˆ์ด์…˜ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๊ณต ์ด๋™ ์‹œ๋ฎฌ๋ ˆ์ด์…˜ nํ–‰ m์—ด์˜ ๊ฒฉ์ž๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฒฉ์ž์˜ ๊ฐ ํ–‰์€ 0, 1, ..., n-1๋ฒˆ์˜ ๋ฒˆํ˜ธ, ๊ทธ๋ฆฌ๊ณ  ๊ฐ ์—ด์€ 0, 1, ..., m-1๋ฒˆ์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ˆœ์„œ๋Œ€๋กœ ๋งค๊ฒจ์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‹น์‹ ์€ ์ด ๊ฒฉ์ž์— ๊ณต์„ ํ•˜๋‚˜ ๋‘๊ณ , ๊ทธ ๊ณต์— ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ฟผ๋ฆฌ programmers.co.kr Solution ํ•ด๋‹น ๋ฌธ์ œ๋Š” ํšจ์œจ์„ฑ์ด ํ•ต์‹ฌ์ธ ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค. ์ตœ๋Œ€ ํ–‰๊ณผ ์—ด์ด ๊ฐ 10^9, ์ตœ๋Œ€ ์ฟผ๋ฆฌ ๊ฐฏ์ˆ˜๊ฐ€ 20๋งŒ์œผ๋กœ ์–ด๋งˆ์–ด๋งˆํ•œ ํฌ๊ธฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์–ด ๋งŒ์•ฝ ๋ชจ๋“  ์œ„์น˜์—์„œ ์‹œ๋ฎฌ๋ ˆ์ด์…˜์„ ๋Œ๋ฆด ๊ฒฝ์šฐ ์ตœ๋Œ€ 10^9 * 10^9 * 200000 ์ด ๋ฉ๋‹ˆ๋‹ค. ์‹œ๊ฐ„์ดˆ๊ณผ๋ฅผ ํ”ผํ•˜๊ธฐ ์œ„ํ•ด์„  ๋ชฉ์ ์ง€์—์„œ๋ถ€ํ„ฐ ์ฟผ๋ฆฌ์˜ ์—ญ์ˆœ์œผ๋กœ ๋˜๋Œ์•„๊ฐ€๋ฉด์„œ ๊ฐ€๋Šฅํ•œ ๋ฒ”์œ„๊ฐ€ ์–ด๋””๊นŒ์ง€์ธ์ง€๋ฅผ ์ฒดํฌํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๋ก  ์„ค๋ช… ์•„๋ž˜์™€ ๊ฐ™์ด ๋ชฉ์ .. 2021. 11. 15.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€1 ์Šคํƒ€ ์ˆ˜์—ด Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์Šคํƒ€ ์ˆ˜์—ด programmers.co.kr Solution 1. a์— ์žˆ๋Š” ์ˆซ์ž๋“ค์˜ ๊ฐฏ์ˆ˜๋ฅผ ์„ธ์ค€๋‹ค. ์ˆซ์ž๋“ค์˜ ๊ฐฏ์ˆ˜๋ฅผ ์„ธ์ฃผ๋Š” ์ด์œ ๋Š” ๊ฐฏ์ˆ˜๊ฐ€ ๋งŽ์€ ์ˆซ์ž๋กœ ์ •๋ ฌํ•˜์—ฌ ์‹œ๊ฐ„ ์ดˆ๊ณผ๋ฅผ ๋ง‰๊ธฐ ์œ„ํ•ด์„œ ์ž…๋‹ˆ๋‹ค. func countNumbers(a:[Int]) -> [Int:Int] { var countDic:[Int:Int] = [:] for n in a { if countDic[n] == nil { countDic[n] = 1 }else { countDic[n]! += 1 } } return countDic } 2. ๊ฐ ์ˆซ์ž๋“ค์˜ ๊ฐ€์žฅ ๊ธด ๋ถ€๋ถ„ ์ˆ˜์—ด ๊ธธ์ด๋ฅผ ๊ตฌํ•ด์ค€๋‹ค. ๊ฐ„๋‹จํ•˜๊ฒŒ ์„ค๋ช…ํ•˜๋ฉด ๊ฐ ์ˆซ์ž๋“ค์˜ ์•ž ๋’ค๋ฅผ ๋น„๊ตํ•ด์ค๋‹ˆ๋‹ค. ๋งŒ์•ฝ ์•ž๊ณผ ๋’ค ์ค‘ ํ•˜๋‚˜๋ผ๋„ ํ˜„์žฌ ์ˆซ์ž์™€ ๊ฐ™์ง€ ์•Š์€ ์ˆซ์ž๊ฐ€ ์žˆ๋‹ค๋ฉด +2.. 2021. 11. 6.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ํ•˜๋…ธ์ด์˜ ํƒ‘ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ํ•˜๋…ธ์ด์˜ ํƒ‘ ํ•˜๋…ธ์ด ํƒ‘(Tower of Hanoi)์€ ํผ์ฆ์˜ ์ผ์ข…์ž…๋‹ˆ๋‹ค. ์„ธ ๊ฐœ์˜ ๊ธฐ๋‘ฅ๊ณผ ์ด ๊ธฐ๋™์— ๊ฝ‚์„ ์ˆ˜ ์žˆ๋Š” ํฌ๊ธฐ๊ฐ€ ๋‹ค์–‘ํ•œ ์›ํŒ๋“ค์ด ์žˆ๊ณ , ํผ์ฆ์„ ์‹œ์ž‘ํ•˜๊ธฐ ์ „์—๋Š” ํ•œ ๊ธฐ๋‘ฅ์— ์›ํŒ๋“ค์ด ์ž‘์€ ๊ฒƒ์ด ์œ„์— ์žˆ๋„๋ก ์ˆœ์„œ๋Œ€ programmers.co.kr Solution ์ด๋ฒˆ ๋ฌธ์ œ์˜ ํ•ต์‹ฌ์€ ์žฌ๊ท€๋ฅผ ์ด์šฉํ•˜๋Š” ๊ฒƒ ์ž…๋‹ˆ๋‹ค. ์•„๋ž˜์™€ ๊ฐ™์ด n๊ฐœ์˜ ์›ํŒ์ด 1๋ฒˆ ๊ธฐ๋‘ฅ์— ๋ชจ๋‘ ์žˆ์Šต๋‹ˆ๋‹ค. 1. 1๋ฒˆ ๊ธฐ๋‘ฅ์— ์žˆ๋Š” ์›ํŒ ์ค‘ ๊ฐ€์žฅ ๋ฌด๊ฑฐ์šด ์›ํŒ์„ ์ œ์™ธํ•œ ์›ํŒ(n-1๊ฐœ)์„ ๋ชจ๋‘ 2๋ฒˆ ๊ธฐ๋‘ฅ์œผ๋กœ ์˜ฎ๊น๋‹ˆ๋‹ค. 2. ๊ฐ€์žฅ ๋ฌด๊ฑฐ์šด ์›ํŒ์„ 3๋ฒˆ ๊ธฐ๋‘ฅ์œผ๋กœ ์˜ฎ๊น๋‹ˆ๋‹ค. 3. 2๋ฒˆ์— ์žˆ๋Š” n-1๊ฐœ์˜ ์›ํŒ์„ ๋ชจ๋‘ 3๋ฒˆ์œผ๋กœ ์˜ฎ๊น๋‹ˆ๋‹ค. ํ•˜๋…ธ์ด์˜ ํƒ‘์„ ํ‘ธ๋Š” ๊ณผ์ •์„ ๊ฐ„๋‹จํ•˜๊ฒŒ ์„ค๋ช…๋“œ๋ฆฌ๋ฉด ์œ„์™€ ๊ฐ™์ด ์ง„ํ–‰๋ฉ๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ ์—ฌ๊ธฐ์„œ ์˜๋ฌธ์ด.. 2021. 10. 31.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€ 3 ๋‚˜๋จธ์ง€๊ฐ€ 1์ด ๋˜๋Š” ์ˆ˜ ์ฐพ๊ธฐ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋‚˜๋จธ์ง€๊ฐ€ 1์ด ๋˜๋Š” ์ˆ˜ ์ฐพ๊ธฐ ์ž์—ฐ์ˆ˜ n์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. n์„ x๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๊ฐ€ 1์ด ๋˜๋„๋ก ํ•˜๋Š” ๊ฐ€์žฅ ์ž‘์€ ์ž์—ฐ์ˆ˜ x๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”. ๋‹ต์ด ํ•ญ์ƒ ์กด์žฌํ•จ์€ ์ฆ๋ช…๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ œํ•œ์‚ฌํ•ญ ์ž… programmers.co.kr Solution 2๋ถ€ํ„ฐ n-1๊นŒ์ง€ ๋‚˜๋ˆ„๋ฉด์„œ ๋‚˜๋จธ์ง€๊ฐ€ 1์ด ๋‚˜์˜ค๋ฉด ๋ฐ˜ํ™˜ํ•œ๋‹ค. func solution(_ n:Int) -> Int { for i in 2.. 2021. 10. 29.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์›”๊ฐ„ ์ฝ”๋“œ ์ฑŒ๋ฆฐ์ง€2 110 ์˜ฎ๊ธฐ๊ธฐ Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - 110 ์˜ฎ๊ธฐ๊ธฐ 0๊ณผ 1๋กœ ์ด๋ฃจ์–ด์ง„ ์–ด๋–ค ๋ฌธ์ž์—ด x์— ๋Œ€ํ•ด์„œ, ๋‹น์‹ ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ํ–‰๋™์„ ํ†ตํ•ด x๋ฅผ ์ตœ๋Œ€ํ•œ ์‚ฌ์ „ ์ˆœ์œผ๋กœ ์•ž์— ์˜ค๋„๋ก ๋งŒ๋“ค๊ณ ์ž ํ•ฉ๋‹ˆ๋‹ค. x์— ์žˆ๋Š” "110"์„ ๋ฝ‘์•„์„œ, ์ž„์˜์˜ ์œ„์น˜์— ๋‹ค์‹œ ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ programmers.co.kr Solution ์ด๋ฒˆ ๋ฌธ์ œ์˜ ํ•ต์‹ฌ์€ ์Šคํƒ์„ ์ด์šฉํ•ด์„œ ํ’€์–ด์•ผ ํ•˜๋Š” ๊ฒƒ ์ž…๋‹ˆ๋‹ค. 1. ๋ฌธ์ž์—ด์˜ ๋ชจ๋“  "110" ์‚ญ์ œํ•ด์ค€๋‹ค. ์—ฌ๊ธฐ์„œ ์Šคํƒ์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š์œผ๋ฉด 4๋ฒˆ,18๋ฒˆ,19๋ฒˆ,21๋ฒˆ ์—์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋‚˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๋ฌธ์ž ํ•˜๋‚˜์‹ ์Œ“์œผ๋ฉฐ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ๋‘ ๊ธ€์ž์™€ ํ˜„์žฌ ๊ธ€์ž๋ฅผ ๋น„๊ตํ•ด์„œ "110" ์ด๋ผ๋Š” ๋ฌธ์ž๊ฐ€ ๋‚˜์˜ค๋ฉด ์Šคํƒ์˜ ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ๋‘ ๋ฌธ์ž๋ฅผ ์ง€์›Œ์ค๋‹ˆ๋‹ค. "110"์„ ์ง€์› ์„ ๋•Œ ๊ทธ ์ด์ „์— ์žˆ๋˜ ๋ฌธ์ž์™€ ์ดํ›„์— ์žˆ๋˜ ๋ฌธ์ž๊ฐ€ ํ•ฉ์ณ์ ธ์„œ ๋˜ ".. 2021. 10. 27.
[Algorithm] ํ€ต ์ •๋ ฌ(Quick Sort)๋ž€? (feat. Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ๋“œ๋””์–ด ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ๋ง ๊ทธ๋Œ€๋กœ ๋งค์šฐ ๋น ๋ฅธ ์ˆ˜ํ–‰์‹œ๊ฐ„์„ ๊ฐ€์ง„ ํ€ต ์ •๋ ฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค! ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ ํ€ต ์ •๋ ฌ(Quick Sort)์ด๋ž€? ๐Ÿง ํ€ต ์ •๋ ฌ(Quicksort)์€ ์ฐฐ์Šค ์•คํ„ฐ๋‹ˆ ๋ฆฌ์ฒ˜๋“œ ํ˜ธ์–ด๊ฐ€ ๊ฐœ๋ฐœํ•œ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋‹ค๋ฅธ ์›์†Œ์™€์˜ ๋น„๊ต๋งŒ์œผ๋กœ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๋น„๊ต ์ •๋ ฌ์— ์†ํ•œ๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - (์ฐธ๊ณ ๋กœ ๋ฆฌ์ฒ˜๋“œ ํ˜ธ์–ด๊ฐ€ ํ€ต ์ •๋ ฌ์„ ๊ฐœ๋ฐœํ–ˆ์„ ๋‹น์‹œ ๋‚˜์ด๋Š” 26์‚ด์ด๋ผ๊ณ  ํ•˜๋„ค์š”...) ํ•ฉ๋ณ‘ ์ •๋ ฌ๊ณผ ๊ฐ™์ด ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ์†ํ•˜๊ณ  ํ‰๊ท ์ ์œผ๋กœ ๋งค์šฐ ๋น ๋ฅธ ์ˆ˜ํ–‰์†๋„๋ฅผ ์ž๋ž‘ํ•ฉ๋‹ˆ๋‹ค. ํ€ต ์ •๋ ฌ ๊ณผ์ • ๐Ÿ”จ ํ€ต ์ •๋ ฌ์„ ํ•˜๊ธฐ ์œ„ํ•ด์„  ํ”ผ๋ด‡(Pivot)์ด ํ•ต์‹ฌ์ด ๋˜๋Š”๋ฐ์š”. ์—ฌ๊ธฐ์„œ ํ”ผ๋ด‡์€ ์–ด๋–ค ๊ฒƒ์ผ๊นŒ์š”? ํ”ผ๋ด‡์€ ๋ฐ”๋กœ ๊ธฐ์ค€์ž…๋‹ˆ๋‹ค. ํ”ผ๋ด‡์„ ๊ฐ€์žฅ ์ฒซ ๋ฒˆ์งธ ์ธ๋ฑ์Šค๋ฅผ ์„ ํƒํ•  ์ˆ˜๋„ .. 2021. 10. 25.
[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.
[Algorithm] ํž™ ์ •๋ ฌ(HeapSort)์ด๋ž€? (feat.Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์ €๋ฒˆ ์‹œ๊ฐ„์— ํž™์ด๋ž€ ์ž๋ฃŒ๊ตฌ์กฐ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด์•˜๋Š”๋ฐ์š”. (ํ˜น์‹œ๋ผ๋„ ์•ˆ๋ณด์‹  ๋ถ„์€ ์—ฌ๊ธฐ ์—์„œ ๋ณด๊ณ  ์™€์ฃผ์„ธ์š”!) ์˜ค๋Š˜์€ ํž™์„ ์ด์šฉํ•ด์„œ ์ •๋ ฌ์„ ํ•˜๋Š” ํž™์†ŒํŠธ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค! ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ ํž™ ์ •๋ ฌ((HeapSort)์ด๋ž€? ๐Ÿง ํž™ ์ •๋ ฌ(Heap sort)์ด๋ž€ ์ตœ๋Œ€ ํž™ ํŠธ๋ฆฌ๋‚˜ ์ตœ์†Œ ํž™ ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•ด ์ •๋ ฌ์„ ํ•˜๋Š” ๋ฐฉ๋ฒ•์œผ๋กœ์„œ, ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌ์„ ์œ„ํ•ด์„œ๋Š” ์ตœ๋Œ€ ํž™์„ ๊ตฌ์„ฑํ•˜๊ณ  ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์„ ์œ„ํ•ด์„œ๋Š” ์ตœ์†Œ ํž™์„ ๊ตฌ์„ฑํ•˜๋ฉด ๋œ๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, ํž™์„ ์ด์šฉํ•ด์„œ ์ •๋ ฌ์„ ํ•˜๋Š” ๋ฐฉ์‹์ด์—์š”. ํž™ ์ •๋ ฌ ๊ณผ์ • ๐Ÿ”จ ํž™ ์ •๋ ฌ ๊ณผ์ •์€ ํž™์—์„œ ์‚ญ์ œ๋ฅผ ๊ตฌํ˜„ํ•  ๋•Œ์™€ ๋˜‘๊ฐ™์•„์š”. ์‚ญ์ œ๊ณผ์ •์ด ์•„๋ž˜์™€ ๊ฐ™์€๋ฐ์š”. ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•˜๊ณ  ๋ฐฐ์—ด์— ์ฐจ๋ก€๋กœ ์Œ“๊ฒŒ๋˜๋ฉด ์–ด๋–ป๊ฒŒ ๋ ๊นŒ์š”? ์ตœ๋Œ€ํž™์ด๋ผ๋ฉด ๊ฐ€์žฅ ํฐ ์ˆซ์ž๊ฐ€ ์ฐจ๋ก€.. 2021. 10. 19.
[Algorithm] ํ•ฉ๋ณ‘ ์ •๋ ฌ(Merge Sort)๋ž€? (feat. Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘ ํ•˜๋‚˜์ธ ํ•ฉ๋ณ‘ ์ •๋ ฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ ๋ถ„ํ•  ์ •๋ณต(Divide and Conquer Algorithm) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€? ๐Ÿก ์œ„์—์„œ ํ•ฉ๋ณ‘ ์ •๋ ฌ์€ ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ค‘ ํ•˜๋‚˜๋ผ๊ณ  ๋ง์”€๋“œ๋ ธ๋Š”๋ฐ์š”. ๊ทธ๋ ‡๋‹ค๋ฉด ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ฌด์—‡์ผ๊นŒ์š”? ๋ง ๊ทธ๋Œ€๋กœ ์ง€๊ธˆ ํ•ด๊ฒฐํ•  ์ˆ˜ ์—†๋Š” ๋ฌธ์ œ๋ฅผ ์ž‘๊ฒŒ ์ชผ๊ฐœ์„œ(๋ถ„ํ• ) ํ’€์–ด๋‚˜๊ฐ€๋Š”(์ •๋ณต) ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ž‘์€ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜์—ฌ ํฐ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ด๋‚˜๊ฐ€๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ•ฉ๋ณ‘ ์ •๋ ฌ์ด๋ž€? ๐Ÿคผ‍โ™€๏ธ ํ•ฉ๋ณ‘ ์ •๋ ฌ ๋˜๋Š” ๋ณ‘ํ•ฉ ์ •๋ ฌ์€ ๋น„๊ต ๊ธฐ๋ฐ˜ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์ผ๋ฐ˜์ ์ธ ๋ฐฉ๋ฒ•์œผ๋กœ ๊ตฌํ˜„ํ–ˆ์„ ๋•Œ ์ด ์ •๋ ฌ์€ ์•ˆ์ • ์ •๋ ฌ์— ์†ํ•˜๋ฉฐ, ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ•˜๋‚˜์ด๋‹ค. ์กด ํฐ ๋…ธ์ด๋งŒ์ด 1.. 2021. 10. 14.
[Swift] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์œ„ํด๋ฆฌ ์ฑŒ๋ฆฐ์ง€ 8์ฃผ์ฐจ ์ตœ์†Œ์ง์‚ฌ๊ฐํ˜• Problem ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - 8์ฃผ์ฐจ [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr Solution 1. ๊ฐ€๋กœ์™€ ์„ธ๋กœ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด์„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค. let sorted = sizes.map{$0.sorted()} 2. ๊ฐ€๋กœ์™€ ์„ธ๋กœ์˜ ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ๊ณฑํ•ด์ค€๋‹ค. return sorted.map{$0[0]}.max()! * sorted.map{$0[1]}.max()! Source Code 2021. 9. 30.
[Algorithm] ์‚ฝ์ž… ์ •๋ ฌ(Insertion Sort) ์ด๋ž€? (feat.Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ํ•™๊ต ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—…์„ ๋“ฃ๋Š” ์ค‘์— ์‚ฝ์ž… ์ •๋ ฌ์„ ๊ตฌํ˜„ํ•ด๋ณด๋Š” ๊ณผ์ œ๊ฐ€ ์žˆ์—ˆ๋Š”๋ฐ... ๋”ฑ ์ด ๋ฐฉ์‹์ด ์–ด๋–ค ๊ฒƒ์ด๊ณ  ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ•ด์•ผ ํ•œ๋‹ค! ๋ผ๊ณ  ๊ตฌ์ฒด์ ์œผ๋กœ ๋– ์˜ค๋ฅด์ง€๊ฐ€ ์•Š๋”๋ผ๊ตฌ์š”... ๊ทธ๋ž˜์„œ ์‚ฝ์ž… ์ •๋ ฌ์ด ๋ฌด์—‡์ด๊ณ  ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ•ด์•ผ ํ•˜๋Š”์ง€์— ๋Œ€ํ•ด ์ •๋ฆฌํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค! ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ ์‚ฝ์ž… ์ •๋ ฌ์ด๋ž€? ์‚ฝ์ž… ์ •๋ ฌ์€ ์ž๋ฃŒ ๋ฐฐ์—ด์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ์•ž์—์„œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ์ด๋ฏธ ์ •๋ ฌ๋œ ๋ฐฐ์—ด ๋ถ€๋ถ„๊ณผ ๋น„๊ตํ•˜์—ฌ, ์ž์‹ ์˜ ์œ„์น˜๋ฅผ ์ฐพ์•„ ์‚ฝ์ž…ํ•จ์œผ๋กœ์จ ์ •๋ ฌ์„ ์™„์„ฑํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. -์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ •๋ ฌํ•˜๋Š” ๊ณผ์ •์„ ์‚ดํŽด๋ณด๋ฉด ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์‚ฝ์ž… ์ •๋ ฌ ๊ณผ์ • 82,10,9,72,31,45,60๋ฅผ ์‚ฝ์ž… ์ •๋ ฌ์„ ํ•˜๋Š” ๊ณผ์ •์€ ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค. 1. ๋จผ์ € ๋งจ ์ฒซ ๋ฒˆ์งธ์ธ 82์™€ ๊ทธ ๋‹ค์Œ ์ˆซ์ž์ธ 10์„ ๋น„๊ตํ•ด์ค๋‹ˆ๋‹ค. 10์ด ๋”.. 2021. 9. 28.
728x90
๋ฐ˜์‘ํ˜•