[プログラマー/python]最大の正方形を検索

4678 ワード
python プログラマ アルゴリズム#アルゴリズム# DP テキストリンク
🧑🏻‍💻 質問リンク

問題を解く


これは동적계획법を使用して解決された問題です.最初は問題をよく読んでいなかったので、変なことをして、もう一度問題を読み直してみると、数字が1の場合だけ正方形を計算していることがわかりました.これからは時間がないので、よく問題を読んで、よく考えてから問題を解く練習をします.
動的計画で解く理由は,エッジの頂点を求めるだけであるため,動的計画法と考えられる.他の人の解題を見てlist comprehesionで計算しますが、私はまだよく知らないので、コードを見ている人にもっと可読性のあるコードを見せたいので、2のfor文を使いました.

コード#コード#

def solution(board):
    answer = 1234

    n = len(board)      # 세로
    m = len(board[0])   # 가로
    
    temp = []

    for i in range(1, n):
        for j in range(1, m):
            # 표에 1인 것만 계산
            if board[i][j] == 1:
                # 위, 옆, 왼쪽 대각선 위를 계산
                board[i][j] = min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1
    
    for i in board:
        for j in i:
            temp.append(j)

    answer = max(temp) ** 2
    return answer

結果


ubuntu apt清華園の鏡像を更新
BOJ 2644:カウントC++