프로그래머스 - 가장 큰 정사각형 찾기 [Python]

 문제

 

 

 문제 상황

 

- 주어진 전체 사각형에서 가장 큰 정사각형을 찾는다. 

 

 

 

 해결 전략

 

- 단순 검색을 통해 구현하면 속도가 O(N^3)로 매우 느리다. 한 변의 길이가 최대 1000이므로 1,000,000,000의 속도는 시간을 초과할 수 밖에 없다. 

 

- 속도 이슈를 해결하기 위해 dp를 사용한다. 기존에 루트 탐색같이 사방을 확인해서 더하는 구조는 사각형이란 특성을 계산할 수 없다. 그래서 단위 사각형을 2x2로 만들어 확인한다.

 

- 2x2사각형의 2행 2열을 기준점으로 잡아 우선 위와 왼쪽 요소를 보고 작은 숫자를 선택한다. 그리고 1행 1열과 그 결과를 비교하여 더 작은 값을 계산하고 1을 더해 2x2에 저장한다. 여기서 더하는 1은 2x2에 존재하는 1을 의미한다. 

 

 

 

 코드

 

def solution(board):
    row = len(board)
    col = len(board[0])
    for i in range(1, row):
        for j in range(1, col):
            if board[i][j] == 1:
                board[i][j] = min(board[i-1][j-1],min(board[i-1][j],board[i][j-1])) + 1
    return max([board[x][y] for x in range(row) for y in range(col)])**2
 

 

 

 

 

 해설

 

- 문제의 상황을 단순 시뮬레이션하여 보드를 분할하여 체크하였더니 속도 오류가 났다. O(N^3)으로 매우매우 느린 코드여서 정확도는 모두 통과했지만 속도에서 문제가 있었다. 이 문제를 읽을 때에는 몰랐지만 이 문제는 dp 문제였다.

 

 

 

 새로 학습한 것 & 실수 

 

- 만약 문제의 조건이 직사각형이라면?

 

- 숫자가 1만 있는 것이 아니라 여러 종류라면 ?

 

 

출처 - https://programmers.co.kr/learn/courses/30/lessons/12905