๊ธ€ ์ž‘์„ฑ์ž: ํƒ์‹œ ์šด์ „์‚ฌ
๋ฐ˜์‘ํ˜•


๐Ÿ‘จโ€๐Ÿซ ๊ฐ€์žฅ ํฐ ์ •์‚ฌ๊ฐํ˜• ๋ฌธ์ œ ํ’€์–ด๋ณด๊ธฐ


๐Ÿ˜ƒ ๋‚˜์˜ ์ฝ”๋“œ

def solution(board):
    width = len(board[0])
    height = len(board)
    for x in range(1,height):
        for y in range(1,width):
            if board[x][y] == 1:
                board[x][y] = min(board[x-1][y-1], min(board[x-1][y], board[x][y-1])) + 1
    return max([item for row in board for item in row])**2

์ด ๋ฌธ์ œ๋ฅผ ์™„์ „ ํƒ์ƒ‰(Brute-force)์œผ๋กœ ํ‘ผ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ด…์‹œ๋‹ค. board์˜ ๋ชจ๋“  ์ธ๋ฑ์Šค๋ฅผ ํ™•์ธํ•ด์•ผํ•˜๊ณ , ์ •์‚ฌ๊ฐํ˜•์ด ๊ฐ€์žฅ ์ž‘์€ 1๋ถ€ํ„ฐ ์ตœ๋Œ€ ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜•๊นŒ์ง€ ํ™•์ธํ•˜๊ฒŒ ๋œ๋‹ค๋ฉด ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(n^3)์ด ๋  ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๋ฌธ์ œ๋ฅผ ์ œ์ถœํ•˜๊ฒŒ๋˜๋ฉด ํšจ์œจ์„ฑ ํ‰๊ฐ€์—์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๋ฅผ ๋ฐ›๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ค„์ด๊ธฐ ์œ„ํ•œ ๋‹ค๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋ฐ”๋กœ DP์ž…๋‹ˆ๋‹ค.


DP(Dynamic Programming)๋ฅผ ์ด์šฉํ•ด์•ผํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. DP์— ๋Œ€ํ•ด์„œ ๊ฐ„๋‹จํ•˜๊ฒŒ ์„ค๋ช…๋“œ๋ฆฌ์ž๋ฉด ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ถ€๋ถ„ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ํ‘ผ ๋’ค, ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ํ† ๋Œ€๋กœ ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค. ๋ฌธ์ œ๋ฅผ ๋‚˜๋ˆ„์–ด์„œ ํ‘ผ๋‹ค๋Š” ์ ์—์„œ ๋ถ„ํ•  ์ •๋ณต๊ณผ ๋น„์Šทํ•˜์ง€๋งŒ, ํ•œ ๊ฐ€์ง€ ๋‹ค๋ฅธ ์ ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋ถ„ํ•  ์ •๋ณต์€ ๋ฌธ์ œ๋ฅผ ๋ถ„ํ•  ํ–ˆ์„ ๋•Œ ๊ฒน์น˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ•˜์ง€ ์•Š์ง€๋งŒ, DP๋Š” ๊ฒน์น˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ•ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ DP์—์„œ๋Š” ๋ฉ”๋ชจ์ด์ œ์ด์…˜(memoization)์ด๋ผ๋Š” ๊ธฐ๋ฒ•์„ ํ†ตํ•ด ๋ฐ˜๋ณต์œผ๋กœ ์ธํ•œ ๊ณ„์‚ฐ์„ ์ค„์—ฌ์ฃผ๋Š” ๊ณผ์ •์ด ์ถ”๊ฐ€์ ์œผ๋กœ ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.


์ด ๋ฌธ์ œ์—์„œ๋Š” ์™ผ์ชฝ ์œ„๋ถ€ํ„ฐ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋ฅผ ์—…๋ฐ์ดํŠธ ํ•ด๊ฐ€๋ฉด์„œ ์ด๋ฅผ ์ด์šฉํ•˜์—ฌ ์ตœ๋Œ€ ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜•์„ ์ฐพ๋Š” ๋ฐฉ์‹์„ ํƒํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. 0์ด ์•„๋‹Œ ์ธ๋ฑ์Šค์˜ ๊ฐ’์„ ์™ผ์ชฝ, ์™ผ์ชฝ ์œ„, ์œ„ ์ด ์„ธ ๊ณณ์„ ํ™•์ธํ•˜์—ฌ ๊ฐ’์ด ๊ฐ€์žฅ ๋‚ฎ์€ ์ธ๋ฑ์Šค์˜ ๊ฐ’๋ณด๋‹ค 1 ํฌ๊ฒŒ ์—…๋ฐ์ดํŠธํ•ด์ค๋‹ˆ๋‹ค. ์ „์ฒด ์ง์‚ฌ๊ฐํ˜•์„ 2 X 2์˜ ์ž‘์€ ์ •์‚ฌ๊ฐํ˜• ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ํ’€๊ณ  ์ด ์ •๋ณด๋Š” ๋‹ค๋ฅธ ์ธ๋ฑ์Šค์—์„œ ์‚ฌ์šฉ๋˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

Written with StackEdit.


๋ฐ˜์‘ํ˜•