[프로그래머스] [Level 2] [다이나믹 프로그래밍] 가장 큰 정사각형 찾기

가장 큰 정사각형 찾기

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

 

 

• 다른 사람 풀이
  • 동적 프로그래밍(DP)
    • 현재 위치의 board값이 1일 때 '현재의 위치에서 가능한 최대 크기의 정사각형의 한 변의 길이'
    • = 현재 위치 [i][j]일 때: dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 세 값을 비교했을 때 가장 작은 값에 1을 더한 값
  • 각 줄의 최댓값 끼리 비교해서 최댓값 구함

풀이 출처: [Python] 프로그래머스 level2 가장 큰 정사각형 찾기 (동적 프로그래밍, dp)

 

 

 

 

 

if board[i][j] == 1:

board[i][j] = min(board[i-1][j-1], board[i-1][j], dp[i][j-1]) + 1
    

 

 

 

def solution(board):
    n = len(board)
    m = len(board[0])
    
    # 2중 포문으로 연산
    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