[CodeKata] 프로그래머스 : 3.2(화), 가장 큰 정사각형 찾기

🥋 Ooooth!! (Level 2)

 

🧮 풀이

* 정확성 테스트 1개 실패, 효율성 테스트 실패로 통과하지 못했다.

function solution(board) {
  let answer = 1;
  for (let i = 0 ; i < board.length-answer ; i++) {
    for (let j = 0 ; j < board[0].length-answer ; j++) {
      if (board[i][j] === 1) {
        while (true) {
          if (i+answer > board.length-1 || j+answer > board[0].length-1) {
            break;
          }
          answer++;
          if (board.slice(i, i+answer).map(row => row.slice(j, j+answer)).flat().includes(0)) {
            answer--;
            break;
          }
        }
      }
    }
  }
  return answer*answer;
}

1. answer은 우리가 누적할 정답이자, 정사각형 최대 길이이다. (반환값은 answer 제곱)
2. board를 이중for문으로 순회하며 board[i][j]가 1인 곳을 확인한다. answer를 빼는 이유는, 현재 최대길이보다 작은 탐색을 제거
3. i+answer, j+answer 가 한 변의 길이를 초과하면 사각형을 만들수 없으므로 break.
4. answer를 1을 증가시키고, 만약 자른 정사각형에 0이 포함되어있다면 answer를 다시 1 감소시키고 break.

 

 

🖇 리뷰

// 다이나믹 프로그래밍(Dynamic Programming)으로 푸는 문제
function solution(board)
{
    var x_len = board[0].length
    var y_len = board.length
    var answer = 0
    
  // 배열의 행과 열이 1이면 정사각형은 무조건 1이 나온다. // 0이 나올수도 있긴함.
    if(x_len < 2 || y_len <2 ) return 1
    
  // 1부터 쭉 탐색하면서 자신의 왼쪽 왼쪽상단, 상단 3개의 값을 비교하며 값을 채워넣는다.
    for(var i=1;i<y_len;i++){
        for(var j=1;j<x_len;j++){
            if(board[i][j]>0){
                let min = Math.min(board[i-1][j-1], board[i][j-1], board[i-1][j])
                board[i][j] = min+1
            } 
            if(answer < board[i][j]){
                answer = board[i][j]
            }
        }
    }
    return Math.pow(answer, 2)
}

* 출처 : javascriptvelog.io/@kimtaeeeny/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%9E%A5-%ED%81%B0-%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95-%EC%B0%BE%EA%B8%B0-javascript

 

동적 프로그래밍을 활용한 문제였다. 2중 for문으로 board를 순회하며, board[i][j] = 1인 지점을 잡는다.

여기서, 좌 / 상 / 좌상 전값들의 최소값 + 1 이, 현재지점까지 만들수 있는 정사각형의 최대 변 길이가 되는 것이다.

동시에, 최대값을 최신화하고 마지막으로 제곱값을 반환하면 정답이 된다.

 

 

* 동적 프로그래밍(DP, Dynamic Programming)

 

큰 문제를 작은 문제로 나누어 푸는 패턴을 일컫는 말이다. 분할정복과 비슷하지만, 차이점은 작은 문제를 반복하지 않는다는 것이다.

• 작은 문제가 반복이 일어나는 경우, 같은 작은 문제는 모두 정답이 같은 경우 적용할 수 있다.
• 반복하지 않도록 작은 문제 결과를 저장 및 재활용한다. 이를, 메모이제이션(Memoization) 혹은 캐싱(Cache) 라고 한다.

대표적인, 동적 프로그래밍의 예로 피보나치 수열이 있다.

피보나치 수열은, FIBO(3)을 FIBO(2)와 FIBO(1)로, 다시 FIBO(4)는 FIBO(3)과 FIBO(2)로 하위값들을 모으는 계산법이다.

 

동적 프로그래밍을 구현하는 2가지 방법이 있는데, Bottom-up 과 Top-down 이다.

 

1) Bottom-up

작은 문제부터 차근차근 메모이제이션 하면서 해결하는 방법이다. 오늘 문제도 Bottom-up 이 되겠다.

int fibonacci(int n)
{
    dp[0] = 0, dp[1] = 1;
    for (int i = 2; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];
}

 2) Top-down

큰 문제를 진행하다 풀리지 않는다면 작은 문제로 접근하는 방법이다. 재귀함수를 사용하는 경우가 많으며, 바텀업에 비해 가독성이 좋다.

int fibonacci(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;

    if (dp[n] != -1) return dp[n];

    dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return dp[n];
}

 * 출처 : kyun2da.github.io/2020/01/19/DynamicProgramming/