[DP] 가장 큰 정사각형 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

 

 

 

1번째 풀이 (성공)

그림을 그리다 보니

현재위치에서 가장 큰 정사각형의 변의 길이는

현재위치의 위, 왼쪽, 왼쪽 위 대각선의  값 중 최솟값 + 1 임을 알아냈다.

예를 들어 첫 번째 그림에서 [2, 2]가 현재 위치이면 up은 1, left: 1, cross: 1로 가장 작은 수는 1이고 1+1이 가장 큰 정사각형 변의 길이가 된다. 따라서 가장 큰 정사각형 변의 길이를 dp에 정리하면 가장 큰 넓이도 구할 수 있다.

 

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

board

0	1	1	1
1	1	2	2
1	2	2	3
0	1	2	3

r, c까지 최대 정사각형 변의 길이

 

점화식

board[r][c] = Math.min(board[r-1][c-1], board[r][c-1], board[r-1][c]) + 1

 

 

DP란?

큰 문제를 작은 문제로 쪼개서 그 답을 저장해 두고 재활용

재귀와 다른 점?

일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산을 한다

O(n^2) → O(f(n)) 로 개선가능

DP는 언제 쓰나?

• 작은 문제를 풀어나감으로 큰 문제의 답을 구할 수 있다 (피보나치처럼)
• 재귀함수가 시간초과 날 때

 

전체코드

function solution(board)
{
    let answer = 0;
    const row = board.length;
    const col = board[0].length;
    // 1항이나 1열이면 최대크기는 1
    if (row === 1 || col === 1) return 1;
    
    for (let r = 1; r < row; r++) {
        for (let c = 1; c < col; c++) {
            if (board[r][c] > 0) {
                const up = board[r-1][c];
                const left = board[r][c-1];
                const cross = board[r-1][c-1];
                // 위, 왼쪽, 대각선중 가장작은 값
                const min = Math.min(up, left, cross);
                board[r][c] = min+1;
                answer = Math.max(answer, board[r][c])
            }
        }
    }
    return answer*answer;
}

 

 

dp로 간단하게 코드를 짤 수 있다는 게 너무 신기하고 재밌다. 내가 지금까지 짠 다른 코드는 뭐람?ㅋㅋㅋ

dp를 더 연습해 봐야겠다.

 

참고