Algorithm/DP
[프로그래머스 lv2] 가장 큰 정사각형 찾기
09009
2023. 10. 15. 20:44
문제 보기
https://school.programmers.co.kr/learn/courses/30/lessons/12905
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
참고 및 출처
설명 GOAT
너무 잘되어있어서 여기 보고 이해함
[Python] 프로그래머스 level2 가장 큰 정사각형 찾기 (동적 프로그래밍, dp)
가장 큰 정사각형 찾기 문제는 동적 프로그래밍으로 풀지 않으면 효율성 테스트에서 통과되지 않는다! 처음에 동적 프로그래밍으로 풀어야 한다는 생각을 하기까지 시간이 좀 걸려서 그 과정까
velog.io
소스 코드
def solution(board):
n,m = len(board), len(board[0])
dp = [[0]*m for _ in range(n)]
dp[0] = board[0]
for i in range(1, n):
dp[i][0] = board[i][0]
for i in range(1, n):
for j in range(1, m):
if board[i][j] == 1:
dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1
answer = 0
for i in range(n):
answer = max(answer, max(dp[i]))
return answer**2