[Python] 가장 큰 정사각형 찾기

코딩테스트 연습 - 가장 큰 정사각형 찾기

풀이

1. 동적계획법(DP)로 풀이

2. 반복문을 통한 완전탐색으로 풀이하기엔 시간복잡도에서 막힌다. (행 : 1,000 열: 1,000)

3. 정사각형이 가능한 최소 변의 길이 2만큼부터 파악.

4. dp 배열에 board의 첫번째 행렬을 넣고 대각선 인덱스에서부터 파악해 나간다.

5. 세 값을 비교해 최솟값에 +1을 해나가고

6. 가장 큰 값의 제곱을 리턴

 

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

 

- DP 배열 사용하지 않고 푼 코드

 

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