[프로그래머스 Lv2] 가장 큰 정사각형 찾기(python)
문제
https://programmers.co.kr/learn/courses/30/lessons/12905
나의 코드 (답안참조)
"""
1. 아이디어
그냥 dp문제라고 직감이 오긴했는데 구현력이 딸려서 실패..
2. 시간복잡도
O(N^2)이지 않나 싶다.. O(N^3)으로 보일 순 있는데 min연산은 3개 하고만 비교하기 때문에 상수값은 무시하는걸로 해도된다.
"""
def solution(board):
n = len(board)
m = len(board[0])
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
line = 0
for i in range(n):
tmp = max(board[i])
line = max(line, tmp)
return line ** 2
느낀점
"""
1. 아이디어
그냥 dp문제라고 직감이 오긴했는데 구현력이 딸려서 실패..
2. 시간복잡도
O(N^2)이지 않나 싶다.. O(N^3)으로 보일 순 있는데 min연산은 3개 하고만 비교하기 때문에 상수값은 무시하는걸로 해도된다.
"""
def solution(board):
n = len(board)
m = len(board[0])
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
line = 0
for i in range(n):
tmp = max(board[i])
line = max(line, tmp)
return line ** 2
어휴.. 완전탐색으로 풀기엔 딱봐도 3중 for문을 넘어갈꺼 같아서 n의 범위를 보니깐 답도 안나와서 dp문제라고 생각하긴 했는데 구현력이 딸려서 실패했다;; dp문제 많이 풀어서 구현 능력좀 길러야지..
참고자료
이 문제에 대해 잘 정리해주셔서 참고 많이 했다.
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
Author And Source
이 문제에 관하여([프로그래머스 Lv2] 가장 큰 정사각형 찾기(python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tyjk8997/프로그래머스-Lv2-가장-큰-정사각형-찾기python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)