Algorithm/programmers/다이나믹 프로그래밍/level2/ 가장 큰 정사각형 찾기(with python)
📖문제
📝풀이과정
board
의 최대 크기가 1000 x 1000이기 때문에 완전 탐색으로 했다가는 시간초과가 난다. 따라서 다이나믹 프로그래밍으로 문제를 푼다.
- 만약 주어진
board
의 행이나 열의 길이가 2 미만인 경우에는board
에 1이 있는지 확인한다.
1이 있다면 가장 큰 정사각형의 크기는 1이므로 1을 리턴하고, 없다면 정사각형이 존재하지 않으므로 0을 리턴한다. board
의 (1,1)부터 시작하여 다음 과정으로 가장 큰 정사각형을 구한다. 현재 위치를 (i, j)라 하자.board
의 (i, j)위치에 있는 값이 1이라면 (i-1, j-1): 왼쪽위, (i, j-1): 위, (i-1, j-1): 아래 위치에 있는 값을 확인한다.- 1번의 세가지 위치에 있는 값들중 최솟값을 구한다.
board
의 (i, j) 위치의 값을(2번에서 구한 최솟값 + 1)
으로 갱신한다.즉, board의 (i, j) 위치의 값은 (i, j)를 오른쪽 아랫점으로 가지는 정사각형의 변의 길이 중 최댓값이 된다.
- 현재까지 구한 정사각형의 변의 길이의 최댓값보다 3번에서 구한 값이 크면
answer
도 3번에서 구한 값으로 갱신한다.
- 그림으로 설명하기
- (0, 0)인 경우
- (2, 3)인 경우
- 최종
⌨코드
def solution(board):
row = len(board)
column = len(board[0])
if row < 2 or column < 2:
for r in board:
if 1 in r:
return 1
return 0
answer = 0
for i in range(1, row):
for j in range(1, column):
if board[i][j] == 1:
board[i][j] = min(board[i-1][j-1], board[i][j-1], board[i-1][j]) + 1
answer = max(answer, board[i][j])
return answer**2
😊 느낀점
def solution(board):
row = len(board)
column = len(board[0])
if row < 2 or column < 2:
for r in board:
if 1 in r:
return 1
return 0
answer = 0
for i in range(1, row):
for j in range(1, column):
if board[i][j] == 1:
board[i][j] = min(board[i-1][j-1], board[i][j-1], board[i-1][j]) + 1
answer = max(answer, board[i][j])
return answer**2
DP로 풀 수 있을 줄은 정말 꿈에도 상상 못했다....
완전 탐색은 아니라는 걸 직감적으로 느꼈지만 다른 방도를 못 구하겠어서 구글링의 힘을 빌렸다🤔 어떻게 이런 생각들을 하시는 거지...ㅜㅜ
오늘 하루 종일 고민했어도 이런 풀이 방법은 생각 못했을 것 같아서 너무 감명받아서 이건 꼭 기록해야겠어서 블로그를 썼다...
Author And Source
이 문제에 관하여(Algorithm/programmers/다이나믹 프로그래밍/level2/ 가장 큰 정사각형 찾기(with python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yellowsummer/Algorithmprogrammers다이나믹-프로그래밍level2-가장-큰-정사각형-찾기with-python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)