(파이썬) 가장 큰 정사각형 찾기 - 동적계획법

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

 

전형적인 동적 계획법 문제입니다.

정사각형의 면적을 동적 계획법 스타일로 처리하는 게 관건이죠. 

주어진 2차원 배열을 그대로 사용하고 대각선 방향, 좌-우, 상-하 셀의 관계를 생각해 봅니다. 

아래 소스를 보시기 전에 직접 표를 작성하면서 아이디어를 떠올려 보세요. 꼭꼭~!!!

동적 계획법 문제는 표 작성 중에 해법이 떠오르는 경우가 많습니다.

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

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.8MB)
테스트 2 〉	통과 (0.05ms, 10.7MB)
테스트 3 〉	통과 (0.07ms, 10.8MB)
테스트 4 〉	통과 (0.07ms, 10.7MB)
테스트 5 〉	통과 (0.08ms, 10.8MB)
테스트 6 〉	통과 (0.05ms, 10.7MB)
테스트 7 〉	통과 (0.05ms, 10.7MB)
테스트 8 〉	통과 (0.05ms, 10.7MB)
테스트 9 〉	통과 (0.05ms, 10.7MB)
테스트 10 〉	통과 (0.07ms, 10.6MB)
테스트 11 〉	통과 (0.05ms, 10.7MB)
테스트 12 〉	통과 (0.06ms, 10.7MB)
테스트 13 〉	통과 (0.05ms, 10.7MB)
테스트 14 〉	통과 (0.07ms, 10.7MB)
테스트 15 〉	통과 (0.07ms, 10.8MB)
테스트 16 〉	통과 (0.07ms, 10.7MB)
테스트 17 〉	통과 (0.07ms, 10.8MB)
테스트 18 〉	통과 (0.85ms, 11MB)
테스트 19 〉	통과 (0.81ms, 10.9MB)
효율성  테스트
테스트 1 〉	통과 (367.83ms, 737MB)
테스트 2 〉	통과 (384.78ms, 737MB)
테스트 3 〉	통과 (381.37ms, 737MB)

다음과 같이 코딩할 경우 더 깔끔해 보입니다만.. 

solution([[0], [1]] 경우를 통과할 수 없습니다. (속도도 더 느립니다)

def solution(board):
    max_num = 0
    for i in range(1, len(board)):
        for j in range(1, len(board[0])):
            if board[i][j] == 1:
                board[i][j] = 1 + min(board[i-1][j], board[i][j-1], board[i-1][j-1])
                max_num = max(board[i][j], max_num)
    return max_num ** 2
    
    
"""
테스트 1 〉	실패 (0.19ms, 10.9MB)
테스트 2 〉	통과 (0.05ms, 10.8MB)
테스트 3 〉	통과 (0.07ms, 10.8MB)
테스트 4 〉	통과 (0.08ms, 10.8MB)
테스트 5 〉	통과 (0.09ms, 10.7MB)
테스트 6 〉	통과 (0.05ms, 10.8MB)
테스트 7 〉	통과 (0.04ms, 10.8MB)
테스트 8 〉	통과 (0.04ms, 10.7MB)
테스트 9 〉	통과 (0.05ms, 10.7MB)
테스트 10 〉	통과 (0.08ms, 10.7MB)
테스트 11 〉	통과 (0.05ms, 10.7MB)
테스트 12 〉	통과 (0.06ms, 10.7MB)
테스트 13 〉	통과 (0.05ms, 10.8MB)
테스트 14 〉	통과 (0.07ms, 10.8MB)
테스트 15 〉	통과 (0.07ms, 10.9MB)
테스트 16 〉	통과 (0.08ms, 10.8MB)
테스트 17 〉	통과 (0.08ms, 10.8MB)
테스트 18 〉	통과 (1.17ms, 10.9MB)
테스트 19 〉	통과 (1.03ms, 10.9MB)
효율성  테스트
테스트 1 〉	통과 (486.41ms, 737MB)
테스트 2 〉	통과 (496.95ms, 737MB)
테스트 3 〉	통과 (519.05ms, 737MB)
"""