프로그래머스 - Lv.2 가장 큰 정사각형 찾기 / 동적 계획법 (DP)

 

문제는 다음과 같다. 0,1 로 이루어진 이차원 배열에서, 1로 이루어진 가장 정사각형을 만들었을 때 가장 큰 넓이를 구하는 문제다.

그리고 이 문제에 접근하기 위해 동적 계획법(Dynamic Proramming)이라는 개념에 대해 알게 되었는데, 이에 대해 먼저 나눠보기로 한다.

 

동적 계획법(Dynamic Proramming)이란?

입력 크기가 작은 부분 문제들을 모두 해결한 후, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 전체 문제를 해결하는 알고리즘 설계기법이다.

따라서 동적 계획법을 사용하기 위해선

• 큰 문제를 작은 문제로 나눌 수 있어야 하며
• 작은 문제들의 해결 방법은 모두 동일해야 하고
• 작은 문제들의 해결 결과는 한 번만 계산하고 저장해 놓을 수 있어야 한다.

 

피보나치 수열은 동적 계획법을 실행할 수 있는 대표적인 문제인데, 4번째 피보나치 수를 구하기 위한 예시를 들어본다.

function fibonacci(n) {
  let arr = [1,1] // 작은 문제들의 해결 결과는 한 번만 계산하고 저장해 놓을 수 있어야 한다.
  
  for(let i = 0 ; i < n ; i++) // 큰 문제를 작은 문제로 나눌 수 있어야 하며
    arr.push(arr.at(-2) + arr.at(-1)) // 작은 문제들의 해결 방법은 모두 동일해야 하고
  
  console.log(arr) // [ 1, 1, 2, 3, 5, 8 ]
  return arr[n-1] // 3
}

fibonacci(4)

만든 로직은 다음과 같다.

피보나치 수의 기본인 1번째, 2번째 수는 1로 정의하여 배열로 둠

이후, n번째 피보나치 수를 구하기 위해서는 n-2번째 수와 n-1번째 수를 합쳐 배열에 저장하는 방식이다.

 

이제 포스팅의 목적이었던 가장 큰 정사각형 찾기 문제로 넘어와 풀이를 이어나가본다.

function solution(board) {
  if(board.length < 2 && board[0].length < 2) return 1
  let result = 0
  for(let i = 1 ; i < board.length ; i ++) {
    for(let j = 1 ; j < board[0].length ; j++) {
      if(board[i][j] === 0) continue
      else {
         board[i][j] = Math.min(board[i-1][j], board[i][j-1], board[i-1][j-1]) + 1
         if(board[i][j] > result) result = board[i][j]
      }
    }
  }
  return Math.pow(result,2)
}

 

해당 풀이를 요약하자면, 이중 반복문에서 board[i][j]에 접근할 때마다, 해당 값이 정사각형이 될 수 있는지 검증하고 이를 board 자체에 저장해가며 이어진다.

이때, board[i][j] === 0인 경우, 직사각형이 되기 위한 조건을 만족하지 못하기 때문에, continue를 사용하여 반복문을 스킵,

그게 아닌 경우라면, 좌상단 & 상단 & 좌단의 최솟값에서 +1를 더한 값을 board[i][j]의 대입한다.

 

이때 여기서 사용하는 최솟값의 의미가 중요한데, 아래의 그림으로 이해하면 좀 더 편하다.

(빗금으로 표시된 부분 : 검증을 진행하는 좌상단 & 상단 & 좌단 / 색으로 채워진 부분 : 로직을 진행하는 board[i][j])

첫번째 표의 경우는, 좌상단이 0이기 때문에, board[i][j]를 기준으로 변 길이가 2이상인 정사각형을 만들 수 없는 조건이다.

두번째 표의 경우는, 모두 1이상으로 정사각형을 만들 수 있는 기준을 만족하기 때문에, 로직 실행 후 board[i][j]에 2가 대입된다.

따라서 여기서 사용하는 최솟값은 해당 board[i][j]가 정사각형을 만들 수 있는지를 파악하는 근간이 되는 요소로 사용된다고 볼 수 있다.

 

그리고 result 변수를 활용하여 가장 큰 값을 기록함으로써 값을 도출해내었다.