[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 ..