[프로그래머스] '가장 큰 정사각형 찾기' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

 

예를 들어

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

 

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

 

1	2	3	4
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	return
[[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

알고리즘 분석

 

• 나의 풀이 ( 효율성 검사 탈락 )

def solution(board):
    h, w = len(board), len(board[0])
    side = min(h, w)
    for unit in range(side, 0, -1):
        for i in range(h-unit+1):
            for j in range(w-unit+1):
                for u in range(unit):
                    if 0 in (board[i+u][j:j+unit]):
                        break
                else:
                    print(unit ** 2)
                    return unit ** 2
    return 0

 

 

• 다른사람의 풀이

# 동적계획법(DP)을 이용한 풀이 
def solution(board):
    ss = {}
    answer = 0
    for y, line in enumerate(board):
        for x, v in enumerate(line):
            if v == 0:
                continue
            ss[(x,y)] = s = min(
                ss.get((x-1,y), 0),
                ss.get((x,y-1), 0),
                ss.get((x-1,y-1), 0)
            ) + 1
            answer = max(answer, s ** 2)
    return answer

 

DP에 대한 설명과 그림이 잘 나타낸 블로그가 있습니다. 

이해가 잘 안된다면 다음 블로그를 확인하시길 바랍니다. 

 

 

[Programmers]Lv 2.가장 큰 정사각형 찾기

 

 

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