[Programmers] 가장 큰 정사각형 찾기 (동적 프로그래밍, dp)

문제

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다.
표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

입출력

board	                                      answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]   	9
[[0,0,1,1],[1,1,1,1]]	                        4

Solution 1

def solution(board):
    answer = 0
    
    r = len(board) # 행의 수
    c = len(board[0]) # 열의 수
    
    # dp 준비
    dp = [[0]*c for _ in range(r)] # r행 c열의 2차원 리스트
    dp[0] = board[0] # 맨 윗줄 고정
    for i in range(1,r): # 왼쪽 고정
        dp[i][0] = board[i][0]
        
    # 2중 for문 연산
    for i in range(1,r):
        for j in range(1,c):
            if board[i][j]==1:
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1 # 셋 중 제일 작은 값에 +1
                
    # 최대 넓이
    for i in range(r):
        tmp=max(dp[i])
        answer=max(answer,tmp)
    
    return answer**2

• 다른 분의 풀이이다.
• dp라는 이차원 배열에 순차적으로 실행한 값들을 채워 넣으면서 진행한다.
• dp에 저장되는 값은 구하려는 해이다.

끄적

• 동적 프로그래밍 문제가 처음이라 구현하기 어려운 문제였다.

Ref.

• ju_h2.log
  
• 주하히의 기술블로그

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기