가장 큰 정사각형 찾기

 

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

문제풀이

반복문을 여러번 사용하여 n^3 이상의 시간복잡도로 접근해 풀이하게 될 경우 시간 초과가 나기에 dp를 활용해서 풀이해야 한다.

 

• 점화식을 사용할 때 인덱스 오류를 방지하기 위해 정사각형의 변의 크기를 저장할 이차원 배열의 각 행렬의 크기를 한 사이즈 크게 초기화해 준다.
• 정사각형의 변의 크기를 재기 위해 board의 왼쪽, 위쪽 테두리만큼을 제외한 오른쪽 하단 꼭짓점 부분을 기준으로 하는 영역의 위치부터 시작하며 왼쪽, 오른쪽, 왼쪽 대각선을 탐색하며 크기를 잰다. 이때 현재 셀은 이전 셀들의 결과에서 최소 값에 +1을 더한 값으로 갱신해 준다. 즉 이전 셀의 결과가 현재 셀의 결과로 이어진다.
• 정사각형의 최대 면적을 구하려면 이중 가장 큰 정사각 형의 변의 크기를 구해야 하므로 가장 큰 값으로 업데이트해 주고 제곱한 결과를 반환한다.

def solution(board):
    n, m = len(board), len(board[0])
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    max_val = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if board[i - 1][j - 1] == 1:
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
            max_val = max(max_val, dp[i][j])
    return max_val * max_val