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

가장 큰 정사각형 찾기(Lv.2)

문제 요구사항

• 위 그림과 같이 0 또는 1로 채워진 board가 주어질 때,
  1로 이루어진 가장 큰 정사각형을 찾아야 한다.

• 단 board의 크기는 1000*1000 이하이다.

문제 접근

• 우선 처음에 누적합을 이용해 풀어보려다 실패했다.
• 누적합을 이용해도 N*M번 순회를 해야하는 건 똑같았고, 시간초과도 나고 로직도 틀렸다.

DP로 접근

• 제한 시간에 문제를 풀지 못해서 풀이를 보고 풀었지만 아직 완벽하게 이해하지 못했다.

점화식

DP[i][j] = min(DP[i][[j-1], DP[i-1][j], DP[i-1][j-1]) + 1

식을 보면 알겠지만 DP[i][j]는 좌, 상, 좌상단 값 중 가장 작은 값 + 1 을 값으로 가진다.

그림으로 그려보았는데 그려놓고 보니 좀 난잡하다.

코드

def solution(board):
    answer = 0
    board = [[0] * len(board[0])] + board
    board = [[0]+b for b in board]
    
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] != 0: # 당연히 현재 위치가 0이 아니어야 한다.
                board[i][j] = min(board[i][j-1], board[i-1][j], board[i-1][j-1])+1
                answer = max(board[i][j], answer)

    return answer**2

누적합 이용 주의

• 누적합은 DP의 한 형태일 뿐인데 요즘 너무 문제들이 너무 누적합으로 보인다.
• 누적합은 많은 경우에서 의도와 달리 시간복잡도를 줄여주지 못한다.
• 문제가 누적합으로 시간복잡도가 줄어들 문제인지 먼저 판단할 수 있어야 한다.

어렴풋이 이해는 했지만 솔직히 아직 비슷한 문제를 풀 수 있을지 의문이 든다.
비슷한 문제들을 더 풀어봐야겠다.