프로그래머스 algorithm study python DP

파이썬 알고리즘 : 가장 큰 정사각형 찾기

DP

2023년 12월 03일 알고리즘 문제풀이

문제

가장 큰 정사각형 찾기

난이도

Lv.2

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def solution(board):
    answer = 1
    p = len(board)
    q = len(board[0])
    dp = [[0 for _ in range(q)] for _ in range(p)]
    dp[0] = board[0]
    for i in range(p):
        dp[i][0] = board[i][0]
    
    for a in range(p):
        for b in range(q):
            if a-1>=0 and b-1>=0 and board[a][b]==1:
                dp[a][b] = min(dp[a-1][b-1],dp[a-1][b],dp[a][b-1])+1
                answer = max(answer,dp[a][b])
    return answer*answer

위 코드는 정확성은 통과했지만 효율성에서 문제를 겪었다. 이 로직은 board 상 1인 좌표마다 검사를 해 가장 큰 사각형의 한 변의 길이가 몇인지 모두 탐색한다. board의 좌표 갯수는 1000000 인데, 이를 평균적으로 500개씩 탐색하면 500000000(5억)이나 수행해야 한다. 결국 아래처럼 고쳐 통과되었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def solution(board):
    answer = 0
    p = len(board)
    q = len(board[0])
    dp = [[0 for _ in range(q)] for _ in range(p)]
    dp[0] = board[0]
    for i in range(p):
        dp[i][0] = board[i][0]

    for a in range(p):
        for b in range(q):
            if a-1>=0 and b-1>=0 and board[a][b]==1:
                dp[a][b] = min(dp[a-1][b-1],dp[a-1][b],dp[a][b-1])+1
    for i in range(p):
        tmp = max(dp[i])
        answer = max(answer,tmp)
    return answer*answer

dp[a][b] 는 dp[a-1][b], dp[a][b-1], dp[a-1][b-1] 이 모두 1이어야 2가 된다. 하나라도 0이라면 최솟값에 1을 더하기 때문에 1로 유지된다. 이 규칙은, 3개가 모두 1이면 길이가 1인 사각형 1개가 확보되기 때문에 성립한다. 이후 나타날 사각형은 지금 발견한 이 사각형을 포함하기 때문에 1을 더해준 채로 진행해도 무방하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def solution(board):
    answer = 0
    p = len(board)
    q = len(board[0])
    dp = [[0 for _ in range(q)] for _ in range(p)]
    dp[0] = board[0]
    for i in range(p):
        dp[i][0] = board[i][0]

    for a in range(p):
        for b in range(q):
            if a-1>=0 and b-1>=0 and board[a][b]==1:
                dp[a][b] = min(dp[a-1][b-1],dp[a-1][b],dp[a][b-1])+1
                answer = max(answer,dp[a][b])
    return answer*answer

또 궁금했던 것은, 위 코드처럼 최댓값을 찾는 과정에서 answer를 dp 배열을 결정할 때마다 비교하면 안되는지 였다. 기존 정답에는 모두 확정된 후에 찾도록 작성되어 있다. 다음과 같은 사례를 생각해보자. 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0

첫번째 코드에서는 가장 작은 정사각형의 크기가 1이라고 나오지만 두번째 코드에서는 0이라고 나온다. a와 b는 0이 아닌 1일 떄부터 반복문이 실행되는데, 이후 board 값은 모두 0이기 때문에 answer가 1로 업데이트 될 수 없기 떄문이다.

CATALOG
    algorithm