[알고리즘] 쿼드압축 후 개수 세기 (Javascript)

자바스크립트와 함께하는 알고리즘 11일차

코딩테스트 연습 - 쿼드압축 후 개수 세기

아이디어

범위만 다른 정사각형에서 동일한 작업을 반복하기 때문에 재귀 함수를 통해 풀 수 있습니다.

재귀 함수의 탈출 조건으로는 제일 작은 정사각형(크기가 1인 정사각형)이 됐을 때와 정사각형의 모든 원소가 0 또는 1로 같을 때입니다.
위 조건을 만족하지 못할 경우 범위를 달리한 정사각형에 동일한 작업을 반복합니다.

해결 방법

문제를 푸는 방법에는 여러 가지 방법이 존재합니다. 전 배열을 이용하는 방법과 좌표와 범위를 이용하는 방법 2가지로 풀었습니다.

배열을 매개변수로 받는 재귀 함수 풀이 방법은 추천하지 않습니다. 좌표로 풀다가 갑자기 꽂혀서 풀었지만, 수행 시간에서 차이가 크게 납니다. 🤯

좌표와 범위를 통해 푸는 방법부터 알아보겠습니다.

1. 매개변수로 x, y, n을 받는 재귀 함수를 작성합니다. x, y는 체크하고자 하는 정사각형의 시작 좌표 그리고 n은 체크하고자 하는 정사각형의 길이입니다.
2. 아이디어에서 언급한 대로 n이 0일 때(크기가 1인 정사각형)와 x부터 x+n 그리고 y부터 y+n까지 차례대로 순환하며 모든 원소가 0 또는 1로 같을 때 재귀 함수를 종료합니다.
3. 2번을 만족하지 못했을 경우 문제의 조건대로 n/2(정사각형의 반)과 자른 정사각형의 시작 좌표에 해당하는 x, y를 가지고 다시 재귀 함수를 호출합니다.

다음은 배열을 통해 푸는 방법입니다.

좌표와 범위를 푸는 방법과 하는 동작은 동일합니다. 단, 매개변수로 받는 배열을 통해 범위를 지정해줘야 하므로 정사각형을 자르듯이 배열을 가공하는 작업이 필요합니다.

보기만 해도 복잡하고 수행 시간은 오래 걸리니 참고만 해주세요. 😂