You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

1 분 소요

1. 문제Permalink

[level 2] 가장 큰 정사각형 찾기 - 12905Permalink

문제 링크

성능 요약Permalink

메모리: 38.7 MB, 시간: 380.09 ms

구분Permalink

코딩테스트 연습 > 연습문제

채점결과Permalink


정확성: 59.6
효율성: 40.4
합계: 100.0 / 100.0

문제 설명Permalink

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 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
입출력 예 설명

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

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

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

2. 해결방법 시간복잡도Permalink

  1. DP O(N^2)

3. 문제 해결 및 코드Permalink

def solution(board = [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]):
# DP 로 해결하기
dp = [[0] * len(board[0]) for _ in range(len(board))]
# 보드의 크기에서 1차원 행렬의 숫자만큼 0으로 가득찬 다차원 행렬 만들기
dp[0] = board[0] # 맨 윗 행렬로 바꾸기
for i in range(1, len(board)): # 이외 행랼 채워주기
dp[i][0] = board[i][0] # 행렬의 첫번째 값 변경해주기
# 2중 반복문
for i in range(1, len(board)):
for j in range(1, len(board[0])):
if board[i][j] == 1: # 만약 위치가 1이라면
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
# dp 위치에서 만들수 있는 가장 큰 사각형을 계산한다
answer = 0
for i in range(len(board)):
tmp = max(dp[i]) # DP로 계산한 가장 큰 값을 도출
answer = max(answer, tmp) # 정답과 비교해서 더 큰 값을 넣는다.
return answer ** 2 # 정사각의 넓이는 한변의 길이의 제곱
view raw 12905.py hosted with ❤ by GitHub

  • 주석을 참고하면서 이해를 돕습니다.Permalink

4. 알고리즘 및 해설Permalink

  1. 문제에서 제시한 보드를 만들어준다.
    • 이때 보드의 크기만큼 1차원 행렬의 숫자와 0으로 가득찬 다차원 행렬을 만든다.
    • 맨 윗 행렬을 문제에서 제시한 보드의 첫번째 행렬로 변경해준다.
  2. 이후 반복문을 통해 행렬의 첫번째 값들을 모두 변경해준다.
  3. 이중 반복문을 통해 1부터 보드의 크기만큼 돌아가되, 이때 j라는 값을 기준으로 보드 내부의 행렬만큼 돌린다.
    • 이때 만약 보드의 위치가 1이라면 dp 위치에서 만들 수 있는 가장 큰 사각형을 계산해준다.
  4. 이후 다시 반복문을 통해 tmp라는 변수를 만들어 DP로 계산한 가장 큰 값을 도출해준다.
    • 이때 answer이라는 변수도 만들어 정답과 비교해서 더 큰 값을 계산해준다.
  5. 최종적으로 결과값에 제곱을 해서 정사각형의 넓이를 출력한다.

참고