[C++] 프로그래머스 :: 가장 큰 정사각형 찾기

안녕하세요 뚜디 입니다 :)

코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스 (programmers.co.kr)

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

< 프로그래머스 - 가장 큰 정사각형 찾기 (LV2) >

---

1. 연습 문제

2. 문제 풀이

3. 소스 코드

4. 결과

---

이번 문제 같은 경우 알고리즘 문제 풀이에서 가장 자주 등자하는

DP(Dynamic Programming) 알고리즘 입니다.

아래 해당 포스팅을 참고해서 DP 관련하여 숙지하고오세요~

[C++] 동적 계획법 Dynamic Programming(DP) 사용법 (tistory.com)

[C++] 동적 계획법 Dynamic Programming(DP) 사용법

[C++] 프로그래머스 :: 땅따먹기 (tistory.com)

[C++] 프로그래머스 :: 땅따먹기

 

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

가 있다면, 가장큰 정사각형의 넓이는 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

 

2. 문제 풀이

DP(Dynamic Programing) 알고리즘을 이용하여 해결해야한다.

1. vector dp를 입력되는 벡터 board와 같게 초기화를 진행한다.
2. answer = board[0][0]을 통해 최소값을 입력해준다.
   => 입력된 벡터의 크기가 작을경우, 최소값을 확인하기위한 용도
3. 반복문을 통해 1,1 부터 진행한다.
   => 주변 정사각형의 유무를 찾기 위해
4. #include <algorithm>의 min()함수를 이용한다
   => "min(5,3) : 3" 최소값을 찾아주는 함수 / "min({5,8,2}) : 2"

 

3. 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> board)
{
    int answer;
    vector<vector<int>> dp(board.size(), vector<int>(board[0].size(), 0));

    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) {
            dp[i][j] = board[i][j];
        }
    }
    answer = board[0][0];

    for (int i = 1; i < board.size(); i++) {
        for (int j = 1; j < board[0].size(); j++) {
            if (board[i][j] == 1) {
                dp[i][j] = min({ dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1] }) + 1;
                if (answer < dp[i][j]) {
                    answer = dp[i][j];
                }
            }
        }
    }
    return answer*answer;
}

 

4. 결과