[프로그래머스 lev2/JS] 쿼드 압축 후 개수 세기

문제 출처

프로그래머스 lev2 - 쿼드 압축 후 개수 세기

나의 풀이 (실패)

function solution(arr) {
}

console.log(
  solution([
    [1, 1, 1, 1, 1, 1, 1, 1],
    [0, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 1, 1, 1, 1],
    [0, 1, 0, 0, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 1],
    [0, 0, 0, 0, 1, 1, 1, 1],
  ])
); // [10,15]

다른 풀이 (통과코드)

동적계획법 - top down

재귀로 넘겨줄 때
=> 시작지점을 넘겨줌으로써, 사각형이 4개로 쪼개져도 다룰 수 있게 해준다.
=> 길이를 넘겨줌으로써 종료조건을 만든다.

각각의 정사각형에 대해 flag를 판단하는데,
=> 전부 일치하면 flag가 true로 유지되면서 countArr를 더해준다.
=> 일치하지 않아 flag가 false가 되면, 길이를 인자로 넘겨줘서 길이가 1이 될때까지 재귀를 돈다.

function solution(arr) {
  const answer = [0,0];
  const len = arr.length; 

  function Quad(size, countArr, start) {
    const first = arr[start[0]][start[1]];
    if (size===1) {
      first === 0 ? countArr[0]++ : countArr[1]++;
      return;
    }

    const half = size/2;
    let flag = true;

    for (let i=start[0]; i<start[0]+size; i++) {
      for (let j=start[1]; j<start[1]+size; j++) {
        if (first !== arr[i][j]) {
          flag=false;
          break;
        }        
      }
      if (!flag) break;
    }

    if (flag) {
      first === 0 ? countArr[0]++ : countArr[1]++;
      return;
    }

    Quad(half, countArr, start);
    Quad(half, countArr, [start[0], start[1]+half]);
    Quad(half, countArr, [start[0]+half, start[1]]);
    Quad(half, countArr, [start[0]+half, start[1]+half]);
    return;
  }

  Quad(len, answer, [0,0]);
  return answer;
}

동적계획법
점화식을 만드는 게 가장 어렵다.

• top down 방식(재귀함수/memoization)
  재귀를 통해 위에서부터 필요한 계산만 하면서 내려오면 된다.
  
• bottom up 방식 (반복문/tabulation)
  n번째 값을 구하기 위해 처음부터 모두 계산하며 올라가야 한다.
  => 1부터 n까지 값을 구해 배열에 저장해놓고 값을 구한다거나
  ...

let dy=Array.from({length:n+2}, ()=>0);
  dy[1]=1;
  dy[2]=2;
  for(let i=3; i<=n+1; i++){
      dy[i]=dy[i-2]+dy[i-1];
  }
  answer=dy[n+1];

참고

[프로그래머스 Level2] 쿼드 압축 후 개수 세기 javascript
Tabulation vs. Memoization