[프로그래머스] 👨‍🏫 가장 큰 정사각형 / Python

👨‍🏫 가장 큰 정사각형 문제 풀어보기

😃 나의 코드

def solution(board):
    width = len(board[0])
    height = len(board)
    for x in range(1,height):
        for y in range(1,width):
            if board[x][y] == 1:
                board[x][y] = min(board[x-1][y-1], min(board[x-1][y], board[x][y-1])) + 1
    return max([item for row in board for item in row])**2

이 문제를 완전 탐색(Brute-force)으로 푼다고 생각해봅시다. board의 모든 인덱스를 확인해야하고, 정사각형이 가장 작은 1부터 최대 크기의 정사각형까지 확인하게 된다면 시간 복잡도는 O(n^3)이 될 것입니다. 이 알고리즘으로 문제를 제출하게되면 효율성 평가에서 시간초과를 받게 됩니다. 따라서 시간 복잡도를 줄이기 위한 다른 알고리즘을 사용해야 합니다. 그 알고리즘이 바로 DP입니다.

DP(Dynamic Programming)를 이용해야하는 문제입니다. DP에 대해서 간단하게 설명드리자면 주어진 문제를 여러 개의 부분 문제로 나누어 푼 뒤, 그 결과를 토대로 주어진 문제를 푸는 방식입니다. 문제를 나누어서 푼다는 점에서 분할 정복과 비슷하지만, 한 가지 다른 점이 있습니다. 분할 정복은 문제를 분할 했을 때 겹치는 문제가 발생하지 않지만, DP는 겹치는 문제가 발생합니다. 따라서 DP에서는 메모이제이션(memoization)이라는 기법을 통해 반복으로 인한 계산을 줄여주는 과정이 추가적으로 필요합니다.

이 문제에서는 왼쪽 위부터 배열의 인덱스를 업데이트 해가면서 이를 이용하여 최대 크기의 정사각형을 찾는 방식을 택하겠습니다. 0이 아닌 인덱스의 값을 왼쪽, 왼쪽 위, 위 이 세 곳을 확인하여 값이 가장 낮은 인덱스의 값보다 1 크게 업데이트해줍니다. 전체 직사각형을 2 X 2의 작은 정사각형 문제로 나누어 풀고 이 정보는 다른 인덱스에서 사용되게 됩니다.

Written with StackEdit.