[ํ๋ก๊ทธ๋๋จธ์ค] ๐จโ๐ซ ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ / Python
๐จโ๐ซ ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ ๋ฌธ์ ํ์ด๋ณด๊ธฐ
๐ ๋์ ์ฝ๋
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.
'Algorithm > Problem Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ๐จ ์นดํซ ๋ฌธ์ / python (1) | 2019.02.15 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ฉโ๐ซ ๋ชจ์๊ณ ์ฌ / python (0) | 2019.02.15 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๐จโ๐ซ ๊ฐ์ฅ ํฐ ์ ์ฌ๊ฐํ / Python (0) | 2019.02.15 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ฉโ๐ซ ํ๋ ฌ์ ๊ณฑ์ / Python (0) | 2019.02.15 |
[ํ๋ก๊ทธ๋๋จธ์ค] โ ์ ํ๋ฒํธ ๋ชฉ๋ก / Python (0) | 2019.02.14 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ทโโ๏ธ ์ ๋ง๋๊ธฐ / Python (2) | 2019.02.14 |
๋๊ธ
์ด ๊ธ ๊ณต์ ํ๊ธฐ
-
๊ตฌ๋
ํ๊ธฐ
๊ตฌ๋ ํ๊ธฐ
-
์นด์นด์คํก
์นด์นด์คํก
-
๋ผ์ธ
๋ผ์ธ
-
ํธ์ํฐ
ํธ์ํฐ
-
Facebook
Facebook
-
์นด์นด์ค์คํ ๋ฆฌ
์นด์นด์ค์คํ ๋ฆฌ
-
๋ฐด๋
๋ฐด๋
-
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
-
Pocket
Pocket
-
Evernote
Evernote
๋ค๋ฅธ ๊ธ
-
[ํ๋ก๊ทธ๋๋จธ์ค] ๐จ ์นดํซ ๋ฌธ์ / python
[ํ๋ก๊ทธ๋๋จธ์ค] ๐จ ์นดํซ ๋ฌธ์ / python
2019.02.15 -
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ฉโ๐ซ ๋ชจ์๊ณ ์ฌ / python
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ฉโ๐ซ ๋ชจ์๊ณ ์ฌ / python
2019.02.15 -
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ฉโ๐ซ ํ๋ ฌ์ ๊ณฑ์ / Python
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ฉโ๐ซ ํ๋ ฌ์ ๊ณฑ์ / Python
2019.02.15 -
[ํ๋ก๊ทธ๋๋จธ์ค] โ ์ ํ๋ฒํธ ๋ชฉ๋ก / Python
[ํ๋ก๊ทธ๋๋จธ์ค] โ ์ ํ๋ฒํธ ๋ชฉ๋ก / Python
2019.02.14