learnings/PS

๋ฌธ์ œ ์„ค๋ช… ์ ์‹ฌ์‹œ๊ฐ„์— ๋„๋‘‘์ด ๋“ค์–ด, ์ผ๋ถ€ ํ•™์ƒ์ด ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ–ˆ์Šต๋‹ˆ๋‹ค. ๋‹คํ–‰ํžˆ ์—ฌ๋ฒŒ ์ฒด์œก๋ณต์ด ์žˆ๋Š” ํ•™์ƒ์ด ์ด๋“ค์—๊ฒŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ฃผ๋ ค ํ•ฉ๋‹ˆ๋‹ค. ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๋Š” ์ฒด๊ฒฉ ์ˆœ์œผ๋กœ ๋งค๊ฒจ์ ธ ์žˆ์–ด, ๋ฐ”๋กœ ์•ž๋ฒˆํ˜ธ์˜ ํ•™์ƒ์ด๋‚˜ ๋ฐ”๋กœ ๋’ท๋ฒˆํ˜ธ์˜ ํ•™์ƒ์—๊ฒŒ๋งŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, 4๋ฒˆ ํ•™์ƒ์€ 3๋ฒˆ ํ•™์ƒ์ด๋‚˜ 5๋ฒˆ ํ•™์ƒ์—๊ฒŒ๋งŒ ์ฒด์œก๋ณต์„ ๋นŒ๋ ค์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ฒด์œก๋ณต์ด ์—†์œผ๋ฉด ์ˆ˜์—…์„ ๋“ค์„ ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— ์ฒด์œก๋ณต์„ ์ ์ ˆํžˆ ๋นŒ๋ ค ์ตœ๋Œ€ํ•œ ๋งŽ์€ ํ•™์ƒ์ด ์ฒด์œก์ˆ˜์—…์„ ๋“ค์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ „์ฒด ํ•™์ƒ์˜ ์ˆ˜ n, ์ฒด์œก๋ณต์„ ๋„๋‚œ๋‹นํ•œ ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด lost, ์—ฌ๋ฒŒ์˜ ์ฒด์œก๋ณต์„ ๊ฐ€์ ธ์˜จ ํ•™์ƒ๋“ค์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด reserve๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ฒด์œก์ˆ˜์—…์„ ๋“ค์„ ์ˆ˜ ์žˆ๋Š” ํ•™์ƒ์˜ ์ตœ๋Œ“๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ..
์ปดํ“จํ„ฐ์‹ค์—์„œ ์ˆ˜์—… ์ค‘์ธ ์ •๋ณด ์„ ์ƒ๋‹˜์€ ๋ƒ‰๋‚œ๋ฐฉ๊ธฐ์˜ ์˜จ๋„๋ฅผ ์กฐ์ ˆํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๋ƒ‰๋‚œ๋ฐฉ๊ธฐ๊ฐ€ ๋ฉ€๋ฆฌ ์žˆ์–ด์„œ ๋ฆฌ๋ชจ์ปจ์œผ๋กœ ์กฐ์ž‘ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ๋ฆฌ๋ชจ์ปจ์˜ ์˜จ๋„ ์กฐ์ ˆ ๋ฒ„ํŠผ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 1) ์˜จ๋„๋ฅผ 1๋„ ์˜ฌ๋ฆฌ๋Š” ๋ฒ„ํŠผ 2) ์˜จ๋„๋ฅผ 1๋„ ๋‚ด๋ฆฌ๋Š” ๋ฒ„ํŠผ 3) ์˜จ๋„๋ฅผ 5๋„ ์˜ฌ๋ฆฌ๋Š” ๋ฒ„ํŠผ 4) ์˜จ๋„๋ฅผ 5๋„ ๋‚ด๋ฆฌ๋Š” ๋ฒ„ํŠผ 5) ์˜จ๋„๋ฅผ 10๋„ ์˜ฌ๋ฆฌ๋Š” ๋ฒ„ํŠผ 6) ์˜จ๋„๋ฅผ 10๋„ ๋‚ด๋ฆฌ๋Š” ๋ฒ„ํŠผ ์ด์™€ ๊ฐ™์ด ์ด 6๊ฐœ์˜ ๋ฒ„ํŠผ์œผ๋กœ ๋ชฉํ‘œ ์˜จ๋„๋ฅผ ์กฐ์ ˆํ•ด์•ผ ํ•œ๋‹ค. ํ˜„์žฌ ์„ค์ • ์˜จ๋„์™€ ๋ณ€๊ฒฝํ•˜๊ณ ์žํ•˜๋Š” ๋ชฉํ‘œ ์˜จ๋„๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ์ด ๋ฒ„ํŠผ๋“ค์„ ์ด์šฉํ•˜์—ฌ ๋ชฉํ‘œ ์˜จ๋„๋กœ ๋ณ€๊ฒฝํ•˜๊ณ ์ž ํ•œ๋‹ค. ์ด ๋•Œ ๋ฒ„ํŠผ ๋ˆ„๋ฆ„์˜ ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•˜์‹œ์˜ค. (์˜ˆ๋ฅผ ๋“ค์–ด, 7๋„์—์„œ 34๋„๋กœ ๋ณ€๊ฒฝํ•˜๋Š” ๊ฒฝ์šฐ, 7 -> 17 -> 27 -> 32 -> 33 -> 34 ์ด๋ ‡๊ฒŒ ์ด 5๋ฒˆ ๋ˆ„๋ฅด๋ฉด ๋œ๋‹ค.) ์ž…๋ ฅ : ํ˜„์žฌ..
๋ถ€๋ชจ๋‹˜์„ ๊ธฐ๋‹ค๋ฆฌ๋˜ ์˜์ผ์ด๋Š” ๊ฒ€์ •/ํฐ ์ƒ‰ ๋ฐ”๋‘‘์•Œ์„ ๋ฐ”๋‘‘ํŒ์— ๊ฝ‰ ์ฑ„์›Œ ๊น”์•„ ๋†“๊ณ  ๋†€๋‹ค๊ฐ€... "์‹ญ(+)์ž ๋’ค์ง‘๊ธฐ๋ฅผ ํ•ด๋ณผ๊นŒ?"ํ•˜๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค. ๋ฐ”๋‘‘ํŒ(19 * 19)์— ํฐ ๋Œ(1) ๋˜๋Š” ๊ฒ€์ • ๋Œ(0)์ด ๋ชจ๋‘ ๊ฝ‰ ์ฑ„์›Œ์ ธ ๋†“์—ฌ์žˆ์„ ๋•Œ, n๊ฐœ์˜ ์ขŒํ‘œ๋ฅผ ์ž…๋ ฅ๋ฐ›์•„ ์‹ญ(+)์ž ๋’ค์ง‘๊ธฐํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•ด๋ณด์ž. ์ž…๋ ฅ ์˜ˆ์‹œ : ๋”๋ณด๊ธฐ 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 ..
๋ณดํ˜ธ๋˜์–ด ์žˆ๋Š” ๊ธ€์ž…๋‹ˆ๋‹ค.