[c++] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค :: ์œ„์žฅ (ํ•ด์‹œ, ๋ฌธ์ œ ํ’€์ด, ์ฝ”๋“œ)
Algorithm ๋ฌธ์ œ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค 2020. 9. 13. 11:05

์œ„์žฅ ๋ฌธ์ œ https://programmers.co.kr/learn/courses/30/lessons/42578 ๋ฌธ์ œ ์„ค๋ช… ์ŠคํŒŒ์ด๋“ค์€ ๋งค์ผ ๋‹ค๋ฅธ ์˜ท์„ ์กฐํ•ฉํ•˜์—ฌ ์ž…์–ด ์ž์‹ ์„ ์œ„์žฅํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์ŠคํŒŒ์ด๊ฐ€ ๊ฐ€์ง„ ์˜ท์ด ์•„๋ž˜์™€ ๊ฐ™๊ณ  ์˜ค๋Š˜ ์ŠคํŒŒ์ด๊ฐ€ ๋™๊ทธ๋ž€ ์•ˆ๊ฒฝ, ๊ธด ์ฝ”ํŠธ, ํŒŒ๋ž€์ƒ‰ ํ‹ฐ์…”์ธ ๋ฅผ ์ž…์—ˆ๋‹ค๋ฉด ๋‹ค์Œ๋‚ ์€ ์ฒญ๋ฐ”์ง€๋ฅผ ์ถ”๊ฐ€๋กœ ์ž…๊ฑฐ๋‚˜ ๋™๊ทธ๋ž€ ์•ˆ๊ฒฝ ๋Œ€์‹  ๊ฒ€์ • ์„ ๊ธ€๋ผ์Šค๋ฅผ ์ฐฉ์šฉํ•˜๊ฑฐ๋‚˜ ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ข…๋ฅ˜ ์ด๋ฆ„ ์–ผ๊ตด ๋™๊ทธ๋ž€ ์•ˆ๊ฒฝ, ๊ฒ€์ • ์„ ๊ธ€๋ผ์Šค ์ƒ์˜ ํŒŒ๋ž€์ƒ‰ ํ‹ฐ์…”์ธ  ํ•˜์˜ ์ฒญ๋ฐ”์ง€ ๊ฒ‰์˜ท ๊ธด ์ฝ”ํŠธ ์ŠคํŒŒ์ด๊ฐ€ ๊ฐ€์ง„ ์˜์ƒ๋“ค์ด ๋‹ด๊ธด 2์ฐจ์› ๋ฐฐ์—ด clothes๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ ์„œ๋กœ ๋‹ค๋ฅธ ์˜ท์˜ ์กฐํ•ฉ์˜ ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”. ์ œํ•œ์‚ฌํ•ญ clothes์˜ ๊ฐ ํ–‰์€ [์˜์ƒ์˜ ์ด๋ฆ„, ์˜์ƒ์˜ ์ข…๋ฅ˜]๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค...

[python]๋ฐฑ์ค€ 1780๋ฒˆ : ์ข…์ด์˜ ๊ฐœ์ˆ˜
Algorithm ๋ฌธ์ œ/BOJ 2020. 3. 6. 22:26

์‹œ๊ฐ„ ์ œํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ ์ œ์ถœ ์ •๋‹ต ๋งž์€ ์‚ฌ๋žŒ ์ •๋‹ต ๋น„์œจ 2 ์ดˆ 256 MB 9503 5463 4173 58.667% ๋ฌธ์ œ N×Nํฌ๊ธฐ์˜ ํ–‰๋ ฌ๋กœ ํ‘œํ˜„๋˜๋Š” ์ข…์ด๊ฐ€ ์žˆ๋‹ค. ์ข…์ด์˜ ๊ฐ ์นธ์—๋Š” -1, 0, 1์˜ ์„ธ ๊ฐ’ ์ค‘ ํ•˜๋‚˜๊ฐ€ ์ €์žฅ๋˜์–ด ์žˆ๋‹ค. ์šฐ๋ฆฌ๋Š” ์ด ํ–‰๋ ฌ์„ ์ ์ ˆํ•œ ํฌ๊ธฐ๋กœ ์ž๋ฅด๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ์ด๋•Œ ๋‹ค์Œ์˜ ๊ทœ์น™์— ๋”ฐ๋ผ ์ž๋ฅด๋ ค๊ณ  ํ•œ๋‹ค. ๋งŒ์•ฝ ์ข…์ด๊ฐ€ ๋ชจ๋‘ ๊ฐ™์€ ์ˆ˜๋กœ ๋˜์–ด ์žˆ๋‹ค๋ฉด ์ด ์ข…์ด๋ฅผ ๊ทธ๋Œ€๋กœ ์‚ฌ์šฉํ•œ๋‹ค. (1)์ด ์•„๋‹Œ ๊ฒฝ์šฐ์—๋Š” ์ข…์ด๋ฅผ ๊ฐ™์€ ํฌ๊ธฐ์˜ 9๊ฐœ์˜ ์ข…์ด๋กœ ์ž๋ฅด๊ณ , ๊ฐ๊ฐ์˜ ์ž˜๋ฆฐ ์ข…์ด์— ๋Œ€ํ•ด์„œ (1)์˜ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค. ์ด์™€ ๊ฐ™์ด ์ข…์ด๋ฅผ ์ž˜๋ž์„ ๋•Œ, -1๋กœ๋งŒ ์ฑ„์›Œ์ง„ ์ข…์ด์˜ ๊ฐœ์ˆ˜, 0์œผ๋กœ๋งŒ ์ฑ„์›Œ์ง„ ์ข…์ด์˜ ๊ฐœ์ˆ˜, 1๋กœ๋งŒ ์ฑ„์›Œ์ง„ ์ข…์ด์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•ด๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1≤N≤3^7, N์€ 3^..

[python] ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ•ด๊ฒฐ ์ „๋žต 1๊ถŒ :: ๊ฒŒ์ž„ํŒ ๋ฎ๊ธฐ (p159) ๋ฌธ์ œ
Algorithm ๋ฌธ์ œ/์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ•ด๊ฒฐ์ „๋žต 2020. 2. 14. 22:53

6.5 ๋ฌธ์ œ : ๊ฒŒ์ž„ํŒ ๋ฎ๊ธฐ (๋ฌธ์ œ ID: BOARDCOVER, ๋‚œ์ด๋„: ํ•˜) ๋ฌธ์ œ H X W ํฌ๊ธฐ์˜ ๊ฒŒ์ž„ํŒ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฒŒ์ž„ํŒ์€ ๊ฒ€์€ ์นธ๊ณผ ํฐ ์นธ์œผ๋กœ ๊ตฌ์„ฑ๋œ ๊ฒฉ์ž ๋ชจ์–‘์„ ํ•˜๊ณ  ์žˆ๋Š”๋ฐ ์ด ์ค‘ ๋ชจ๋“  ํฐ ์นธ์„ ์„ธ ์นธ์งœ๋ฆฌ L์ž ๋ชจ์–‘์˜ ๋ธ”๋ก์œผ๋กœ ๋ฎ๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ ๋ธ”๋ก๋“ค์€ ์ž์œ ๋กญ๊ฒŒ ํšŒ์ „ํ•ด์„œ ๋†“์„ ์ˆ˜ ์žˆ์ง€๋งŒ, ์„œ๋กœ ๊ฒน์น˜๊ฑฐ๋‚˜, ๊ฒ€์€ ์นธ์„ ๋ฎ๊ฑฐ๋‚˜, ๊ฒŒ์ž„ํŒ ๋ฐ–์œผ๋กœ ๋‚˜๊ฐ€์„œ๋Š” ์•ˆ ๋ฉ๋‹ˆ๋‹ค. ๋‹ค์Œ ๊ทธ๋ฆผ์€ ํ•œ ๊ฒŒ์ž„ํŒ๊ณผ ์ด๋ฅผ ๋ฎ๋Š” ๋ฐฉ๋ฒ•์„ ๋ณด์—ฌ์ค๋‹ˆ๋‹ค. ๊ฒŒ์ž„ํŒ์ด ์ฃผ์–ด์งˆ ๋•Œ ์ด๋ฅผ ๋ฎ๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”. ์‹œ๊ฐ„ ๋ฐ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ ํ”„๋กœ๊ทธ๋žจ์€ 2์ดˆ ์•ˆ์— ์‹คํ–‰๋˜์–ด์•ผ ํ•˜๋ฉฐ, 64MB ์ดํ•˜์˜ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•ด์•ผ๋งŒ ํ•ฉ๋‹ˆ๋‹ค. ์ž…๋ ฅ ์ž…๋ ฅ์˜ ์ฒซ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ˆ˜ C(C=0 and tmp[0]=0 and tmp[1]=0 ..