[Algorithm] programmers/가장 큰 정사각형

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

제한사항

표(board)는 2차원 배열로 주어집니다.
표(board)의 행(row)의 크기 : 1,000 이하의 자연수
표(board)의 열(column)의 크기 : 1,000 이하의 자연수
표(board)의 값은 1또는 0으로만 이루어져 있습니다.

접근법

>> 최종 접근법 : dynamic programming
    >> 사실, 내가 어떤 느낌을 갖고 작성하긴 했지만
    >> 느낌 수준을 넘어 타당성을 확실히 확보해야 한다. 
    >> 타당성을 확보한다? 스스로 왜 이렇게 해도 되는지 증명해야 한다는 뜻
    >> wait

>> 초기 접근법 : sliding window and checking 
    >> 효율성 통과 못함

코드_dp

def solution(board): 

    # sliding window 
    h = len(board)
    w = len(board[0])
    dp = [[0 for _ in range(w+1)] for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = board[i][j]

    adj = [[1,0], [1,1], [0,1]]    
    for i in range(h):
        for j in range(w):
            if dp[i][j] and dp[i+1][j+1]:
                dp[i+1][j+1] = max(dp[i+1][j+1], min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1)     
    x = max( [max(row) for row in dp])
    return x*x

코드_sliding window

def solution(board):
    # sliding window 
    h = len(board)
    w = len(board[0])
    n = min(h,w)

    if n==1:
        return 1

    for wsize in range(n, -1, -1):
        limrow = h-wsize+1
        limcol = w-wsize+1
        for row_start in range(0, limrow):
            for col_start in range(0, limcol): 
                expectation = wsize*wsize

                for i in range(row_start, row_start+wsize):
                    if sum(board[i][col_start:col_start+wsize]) == wsize :
                        expectation-=wsize
                    else:
                        break
                if expectation==0:
                    return wsize*wsize