[프로그래머스] 가장 큰 정사각형 찾기 - DP

문제

 

풀이

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 0과 1로 이루어짐.
//[[0,0,0,0]] : 0 , [[0,0,1,0]] : 1
// DP 다이나믹 프로그래밍(또는 동적 계획법)
int solution(vector<vector<int>> board)
{
    int max = 0;
    int space[1001][1001] = {0};
    for(int i=0; i<board.size(); i++){
        for(int j=0; j<board[i].size(); j++){
            space[i+1][j+1] = board[i][j];
        }
    }
    
    for(int i=1; i<board.size()+1; i++){
        for(int j=1; j<board[0].size()+1; j++){
            if(board[i-1][j-1] == 1 )
                space[i][j] = min(space[i][j-1], min(space[i-1][j], space[i-1][j-1])) + 1;
            
            if(space[i][j] > max) max = space[i][j];
        }
    }
    
    return pow(max,2);
}

문제 풀이에 DP알고리즘을 사용하였다.

작은 문제의 해가 곧 큰 문제를 해결할 때 사용되는 알고리즘이다.

 

board와 같은 값을 가지되, 행과 열이 각각 1개씩(모두 0으로 되어있는) 추가된 배열 space를 활용하였다.

행과 열을 하나씩 추가한 이유는 [[0,0,0,1]], [[0],[0],[0],[1]] 일 때의 해를 구하기 위함이다.

 

board배열을 탐색하여 값이 1일경우 space에서 해당 위치(행과 열이 각각 +1 되었음을 고려)의 왼쪽(←), 왼쪽상단(↖︎), 위쪽(↑)의 최솟값을 구한 후 자신의 위치에 그 세 값의 최솟값 + 1을 해준 후 저장한다.

세 값의 최솟값에 + 1 을 해준다는 것은 정사각형의 한 변의 길이가 + 1 된다는 것이다

한 변이 가질 수 있는 최댓값을 구한 후 제곱하여 return 해준다. 

 

 

DP - Dynamic Programming (동적 계획법)

• 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것
• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
• 대표적인 사용 예시로는 피보나치 수열이 있다.

 

DP와 그리디 알고리즘의 차이점

DP (동적 계획법 )

• 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘
• 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택합니다.

그리디 알고리즘(탐욕 알고리즘)

• 그리디 알고리즘은 모든 해를 구하지 않고 순간마다 그 순간에서의 최적의 해를 찾는 방식
• 그리디 알고리즘은 닥치는 순간만을 고려해서 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 수 없다.

즉 DP는 그리디 알고리즘에 비해 시간이 오래 걸리지만, 항상 최적의 해를 구할 수 있다

 

 

 

---

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)

https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP

[자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)