📗 가장 큰 정사각형 찾기

프로그래머스

def solution(board):
    answer = 0
    rows = len(board)
    cols = len(board[0])
    
    dp = [[0] * cols for _ in range(rows)]
    
    for i in range(rows):
        dp[i][0] = board[i][0]
        answer = max(answer, dp[i][0])
        
    for j in range(cols):
        dp[0][j] = board[0][j]
        answer = max(answer, dp[0][j])
    
    for i in range(1, rows):
        for j in range(1, cols):
            if board[i][j] == 1:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                answer = max(answer, dp[i][j])
    
    return answer ** 2

왜 이렇게 풀었을까?

• 주어진 2차원 Board에서 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제였습니다.
• 각 위치에서 만들 수 있는 최대 크기의 정사각형을 계산해야하는데, (i, j)를 오른쪽 아래 꼭짓점으로 하는 정사각형의 변의 길이를 dp 배열에 담아 넓이를 갱신해주었습니다.
• 처음에는 브루트포스나 그리디를 생각했었는데, 시간 복잡도 측면에서 비효율적이라고 판단되어 특정 위치에서의 정사각형의 변의 길이를 계속해서 업데이트해주는 방식인 dp로 문제를 접근해보았습니다.