[파이썬] (level4) 가장 큰 정사각형 찾기

5중 포문 이용하기

데이터 개수 1452행 * 5열 배열일 때 (즉, 7260)개 일때,
100번 실행 결과의 평균

>>> print("실행시간 : ", time.time()-start_time)
1.1673초

아이디어

처음 풀었을 때는 DP의 개념을 몰랐기 때문에 노가다로 한번 풀어봤다.

def findLargestSquare(board):
    # board의 길이를 측정한다. 다만, 전역변수 max_x와 max_y를 좌표값으로 활용해야 하기 때문에 (실제 길이 - 1)을 한다.
    max_x = len(board) - 1
    max_y = len(board[0]) - 1

    max_square = 0 # 정사각형의 최대 넓이
    for x in range(0, len(board)):
        for y in range(0, len(board[x])):
            for index in range(max_x, -1, -1):
                # (x + index와 y + index)는 대각선 방향으로 최대한 뻗을 수 있는 좌표값이다.
                # 전역변수 max_x와 max_y를 활용했다. 이 (max_x, max_y) 범위를 벗어나지 않아야 'O'의 개수를 셀 수 있다.
                if x + index <= max_x and y + index <= max_y:
                    count_o = 0 # 'O'의 개수를 세는 지역변수

                    # m, n은 5시 방향으로 뻗어나가는 대각선의 좌표값이다.
                    for m in range(x + index, x-1, -1):
                        for n in range(y + index, y-1, -1):
                            # 하나씩 m과 n을 줄여나가면서 개수를 센다.
                            if board[m][n] == "O":
                                count_o += 1

                                # 면적을 구하는데, index로 구했다. 면적값을 뭘로 구하던 상관은 없다.
                                # 대신, (면적 값) == (원의 개수)이고, max_square보다 크다면 최대 면적 넓이가 변경된다.
                                if (index+1)**2 == count_o:
                                    if max_square < count_o:
                                        max_square = count_o
                                    else:
                                        continue
    print("max_suqare : ", max_square)
    return max_square

기본적인 개념은 위와 같다. 대각선으로 최대한 뻗을 수 있는 좌표값을 구한 다음에, 원의 개수를 일일이 세는 것이다. x좌표와 y좌표 안에서 또 대각선의 좌표를 설정해줘야 하기 때문에 비효율적인 에너르기파 코드가 나왔다.

DP 이용하기

데이터 개수 1452행 * 5열 배열일 때 (즉, 7260개)
100번 실행 결과의 평균

>>> print("실행시간 : ", time.time()-start_time)
0.0049초

5중 포문을 사용할 때보다 약 성능이 238배 차이난다. 데이터 개수가 많아질수록 이 차이는 심해질 것이다.

아이디어

민기가 DP(Dynamic Programming)의 개념을 알려주었다. Dynamic Programming이란 점화식과 비슷한 듯하다.
전에 나왔던 답을 이용해서 효율적으로 다음 답을 캐치하는 것이다. F(n) = F(n-1) + F(n-2) 꼴을가진 피보나치 수열도 Dynamic Programming의 일부라고 볼 수 있다.

def findLargestSquare(board):
    # 'O'에 해당하는 것을 1로, 'X'에 해당하는 값을 0으로 바꿔준다.
    table = [[1 if x == "O" else 0 for x in sub_board] for sub_board in board]
    max_square = 0
    for x in range(1, len(table)):
        for y in range(1, len(table[x])):
            # 만약 table[x][y]의 값이 0(즉, 'X')라면 정사각형을 만들 수 없으므로 건너 뛴다.
            if table[x][y] == 0:
                continue
            # 해당 좌표 기준(x,y) : 왼쪽검사(x, y-1), 위쪽 검사(x-1, y), 11시 방향 대각선 검사(x-1, y-1)
            else:
                # 최소값을 하나 뽑아낸다. 차례대로 min(왼쪽 좌표, 위쪽 좌표, 왼쪽 대각선 좌표)를 의미한다.
                _min = min([table[x][y-1], table[x-1][y], table[x-1][y-1]])
                table[x][y] = _min + 1

                # 만약, max_square보다 큰 값이 등장하면, 교체해준다.
                if max_square < table[x][y]:
                    max_square = table[x][y]

    # 넓이를 반환해야 하므로 제곱을 해서 반환한다.
    return max_square**2

아무튼 민기가 가르쳐준 개념에 의하면, DP Table을 새로 만드는 것이 핵심이다. 여기서 0행과 0열을 제외하고 값을 하나씩 채워나간다.
자신이 컴퓨터라고 생각하고, 채워야 할 칸에서 왼쪽, 위, 왼쪽 대각선의 값을 검사한다. 여기서 최소값을 찾아 +1 한 것이 박스 네모칸의 답이다.

나도 처음에 이해가 힘들었지만, 지뢰찾기(?)나 기모으기(?)라고 생각하면 된다.

3개값이 모두 (3, 3, 3)이면 네모 값이 4가 된다.
3개값이 모두 (4, 4, 4)이면 네모 값이 5가 된다.
그런데 3개 값이 각각 (1, 2, 3)이면 네모 값이 2가 된다.

쉽게 말해서, min(왼쪽, 위쪽, 왼쪽 대각선)은 단 가장 작은 하나의 값이 나올 것이다.

여기서 +1 해준 값이 네모 칸에 채워져야 할 값이다.

만약 (0, 5, 9)라면? 정답은 알 수 없다

왜냐하면 네모칸이 0(즉, X였다면) 정사각형을 만들 수 없기 때문에 채워지는 값은 0이 된다.
네모칸이 1(즉, O였다면)되어야 비로소 1이라고 써넣을 수 있다.

이 점만 조심하면 될 듯하다.

문제 출처

https://programmers.co.kr/learn/challenge_codes/189