[python/C++] 가장 큰 정사각형 찾기 / 동적 프로그래밍(DP)

가장 큰 정사각형 찾기 : 동적 프로그래밍(dp)

#include<vector>
using namespace std;

int dp[1001][1001]={0};
int solution(vector<vector<int>> board)
{
	int ans=0;
    int row = board.size();
    int col = board[0].size();
    for(int i = 1; i <= row; ++i)
    	for(int j = 1; j <= col; ++j)
        	if(board[i-1][j-1] != 0 ){
            	dp[i][j] = min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1;
                ans = max(ans, dp[i][j]);
            }
    return ans*ans;
}

 

def solution(board):
    n = len(board)
    m = len(board[0])

    # dp 준비
    dp = [[0]*m for _ in range(n)]
    dp[0] = board[0]
    for i in range(1,n):
        dp[i][0] = board[i][0]
    
    # 2중 for문으로 연산
    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

 

[Python] 동적 계획법(DP: Dynamic Programming)

 

[Python] Dynamic Programming(동적계획법) 알고리즘

https://catnap-jo.tistory.com/111

DP - 점화식의 중요성(BOJ 11052, 16194)