[프로그래머스 level2 가장 큰 정사각형 찾기] 이런 신박한 방법이 있다니!

하..역시 level2 답게 굉장히 어려웠다.. 내 풀이는 효율성테스트를 계속 통과하지 못하여 다른 풀이를 보고 이해해보기로 하였다.

 

오늘 해결해야하는 문제는 다음과 같았다.

programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

[문제 설명]

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

예를 들어

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

[제한사항]

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

 

 

[입출력 예]

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

 

 

후..나는 원래 CNN에서 convolution하는 방법을 응용해보고자 하였다.

filter크기를 1부터 시작하여 행과 열 중 작은 것만큼 필터크기를 증가시켜보면서 만족하는 크기가 있는지 확인하는

방식으로 하였다. 이는 while문 안에 2중 포문이 들어가게 되므로 코드가 많이 복잡하였고, 시간 복잡도 또한 O(n^3)이므로 크게 비효율적일 것 같았다. 

 

따라서 계속 고민을 해보았는데,,, 생각이 도무지 않나서 다른 코드를 참고하게 되었다.

 

이 문제를 해결하기 위해서는 동적 계획법인 Dynamic Programming이 필요하다.

이에 대한 자세한 개념은 자료구조 및 알고리즘에 정리해놓고자 한다.

 

간략히 동적 계획법에 대해 설명하자면 , Polynomial한 시간 안에 문제를 풀기 위해서 이전의 성질을 활용하여 푸는 방법이다. 

 

주어진 코드는 표로 그려보고 이해가 가능했다.

 

[주어진 board]

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

[코드를 적용한 board]

0	1	1	1
1	min(0,min(1,1))+1 = 1	min(1,min(1,1))+1 = 2	min(1,min(1,2))+1 = 2
1	min(1,min(1,1))+1 = 2	min(1,min(1,1))+1 = 2	min(2,min(2,2))+1 = 3
0	0	min(2,min(2,0))+1 = 1	0

각 자리를 검사할 때 0행이거나 0열이 아닌 경우, 

board[i][j]가 1이라면 큰 정사각형을 만들 수 있게 되므로, 앞에서 정의된 board[i-1][j-1]과 board[i-1][j], board[i][j-1]에 들어간 수를 확인하여 해당 자리에서 가장 큰 정사각형을 만드는 경우 변의 길이를 알 수 있게 되는 것이다.

 

이러한 조건을 통해 작성한 최종 코드는 다음과 같게 된다.

def solution(board):
    answer = []
    for i in range(len(board)):
        for j in range(len(board[0])):
            if i==0 or j==0:
                continue
            if board[i][j] != 0:
                board[i][j] = min(board[i-1][j-1],min(board[i-1][j],board[i][j-1]))+1
    

    for i in range(len(board)):
        answer.append(max(board[i]))
    return max(answer)**2

 

솔직히 말해서 이러한 문제를 접하게 될 일은 많은 것 같은데 전혀 감을 잡지 못하였다...

DP와 같이 이전의 상태를 활용하는 문제에 있어 굉장히 약하다는 것을 알 수 있었다..

 

DP에 대해 정리하여 확실히 공부해야겠다..! 이제 만나는 문제들은 적합한 알고리즘을 생각해내어 풀 수 있는가에 초점이 있다고 생각하므로 이에 대해 정리를 하며 문제 푸는 양보다 질에 초점을 두어야 겠다..⭐️