프로그래머스 / 가장 큰 정사각형 찾기 / python

def solution(board):
    column = len(board)
    row = len(board[0])
    dp = [[0] * row for _ in range(column)]
    
    _max = 0
    for i in range(column):
        for j in range(row):
            if i == 0:
                dp[i][j] = board[i][j]
            elif j == 0:
                dp[i][j] = board[i][j]
            else:
                if board[i][j] == 1:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        _max = max(max(dp[i]), _max)
    return _max ** 2

dp 알고리즘으로 해결한 문제
완전탐색으로 문제를 해결할시 시간 복잡도는 O(N^2logn)이다. 최대 크기가 1000 * 1000 이므로 완전탐색 방법으로는 불가능하다.

dp로 해결해야하는데 주어진 board가 1일때 좌, 상, 좌상의 최소값에서 1을 더해준다. -> 이렇게 해줌으로써 정사각형의 최대 크기를 누적해서 저장할 수 있다.