[프로그래머스] LV2 | DP? | 가장 큰 정사각형 Python

[프로그래머스] LV2 | DP? | 가장 큰 정사각형 Python

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

프로그래머스

 

 

구상

• DP로 어떻게 푼다는 건지 모르겠어서 솔루션 봄
  • 인덱스를 처음부터 돌고싶어서 그 방향으로 풀어보려고 고집했는데 인덱스 위치는 내 생각보다 중요함.. DP가 이전의 계산값을 활용하는 개념이니 뒤쪽 값을 사용하는 방향으로 설정하는 게 당연했을지도.. 이것저것 해보기
  • 점화식
    • dp테이블에 저장할 값은 정사각형 한 변의 최대 길이이다. (답은 넓이지만.. 이런 유연함도 가질 것)
    • dp[i,j] = min(dp[i-1, j-1], dp[i, j-1], dp[i-1, j]) + 1
    • dp를 생각하는 것보다는 점화식을 생각해내는 게 풀이포인트 였던 것 같다. 아니면 내가 dp를 아직 덜 공부해서 이론이랑 연결이 안되는 건가.. 점화식을 생각하는 거 자체가 dp라고 볼 수 있나
• DP공부 다시해보자
  • 최적 부분 구조, 반복 계산.
  • Bottom-up = 반복문 
  • Top-down = 재귀
  • 점화식을 생각해내고 문제의 변수(i, j 또는 n..)가 무엇인지 파악하기

 

풀이

# v1 : dp 최적부분구조 반복계산. bottom-up(반복문)

def solution(board):
    
    h, w = len(board), len(board[0])
    
    for i in range(h) :
        for j in range(w) :
            
            if board[i][j] == 0 :
                continue
            
            if i==0 or j==0 :
                continue
            
            #주변 정사각형 한 변 값의 최솟값 + 1 이 현위치에서의 정사각형 한 변 최댓값
            board[i][j] = min(min(board[i-1][j], board[i][j-1]), board[i-1][j-1]) + 1
    
    #최댓값 구하기
    max_len = 0
    for boxes in board :
        for box in boxes :
            if max_len < box :
                max_len = box
            
    return max_len**2 #한 변을 넓이로 반환

 

 

 

참고한 글

https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95-%EC%B0%BE%EA%B8%B0-%EB%8F%99%EC%A0%81-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-dp

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