[프로그래머스] 가장 큰 정사각형 찾기

출처:: programmers.co.kr/learn/courses/30/lessons/12905?language=python3

분류:: 완전탐색, dp

 

1. 문제 이해 및 해결과정

 1) dp

- O(n^3)로 완탐하면 시간초과 발생가능성이 있으므로, dp를 고려함 - dp는 만들 수 있는 최대 직사각형의 크기 - board[i][j]가 1일 경우에만, dp = min(board[i-1][j-1],board[i][j-1],board[i-1][j]) + 1

 

2. 풀이방법

  1. dp

def solution(board):
    h=len(board) #세로
    w=len(board[0]) #가로
    
    for i in range(1,h):
        for j in range(1,w):
            board[i][j]=min(board[i-1][j-1],board[i][j-1],board[i-1][j])+1        

    return max([ i  for row in board for i in row ])**2 #최대값을 찾아서 제곱

 

3. 오답원인

 

4. 알게된 점