[프로그래머스] 연습문제 > 가장 큰 정사각형 찾기

programmers.co.kr/learn/courses/30/lessons/12905?language=python3

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

문제 설명

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

예를 들어

1234

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

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

1234

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으로만 이루어져 있습니다.

---

입출력 예

boardanswer

[[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

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

 

---

 

풀이

 

삼중 for문을 사용하여 구현을 하긴 했지만, 효율성 부분에서 실패했다.
한 시간 정도 고민을 해보다가 다른 분의 풀이를 찾아보았다.

먼저, 이 문제에서 사용된 개념은 동적 계획법(DP:Dynamic Programming)을 
사용하여야 한다.

동적 계획법이란
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
분할 정복 순환과 비슷한 개념이지만 다른 점이 있다. 분할 정복 순환은 중복이 발생하지 않지만
동적 계획법은 중복이 발생하므로 메모이제이션(memoization) 기법을 사용하여야 한다.
메모이제이션이란
    메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다

1   1    ==> 왼쪽과 같이 구성되어 있다면 오른쪽 아래 즉 (2,2)가 1일 때 왼쪽 위 (1,1), 위(1,2), 왼쪽(2,1) 중의 최솟값에 1                 을 더한 것으로 기준 좌표 (2,2)의 값을 변경해준다. 
1   1        

1   1    ==> 변경 후에는 좌측과 같이 변경될 것이다. 이렇게 이중 for문을 통해 수행해가며 문제를 작은 문제로 쪼개                      어 해결한다.
1   2 

 

마지막에는 모든 값들 중 max값을 반환해주면 되는데 여기서 사용한 itertools.chain함수는 인자의 값들을 하나로 합쳐주는 함수이다.
chain('ABC', 'DEF') --> A B C D E F
*board와 같이 *를 붙여 2차원 리스트 또한 하나로 합칠 수 있다.

 

 

import itertools
def solution(board):
    M, N = len(board), len(board[0])
    for i in range(1, M):
        for j in range(1, N):
            if board[i][j] == 1:
                board[i][j] = min(board[i-1][j-1], board[i-1][j], board[i][j-1]) + 1
                
    return max(itertools.chain(*board))**2