[programmers][월간 코드 챌린지 시즌1] 쿼드압축 후 개수 세기

문제 : programmers.co.kr/learn/courses/30/lessons/68936

---

크기가 2인 answer 배열을 하나 만들고 각각 0, 1일 때 크기를 저장한다.

arr[sx~ex][sy~ey] 를 탐색하면서 모든 수가 같은지 확인하고 같다면 answer 배열을 갱신하고 같지 않다면 배열을 4분할로 나눠서 다시 판단한다.

이 때 n은 확인하고 있는 배열의 크기로 ex - sx값이라 한다.

1. arr[sx ~ ex - n/2][sy ~ ey - n/2]

2. arr[sx + n/2 ~ ex][sy ~ ey - n/2]

3. arr[sx ~ ex - n/2][sy + n/2 ~ ey]

4. arr[sx + n/2 ~ ex][sy + n/2 ~ ey]

이를 매열 크기가 1일때까지 반복하고 배열 크기가 1이면 arr[탐색중인 인덱스] 값을 answer 배열 인덱스로 배열 값을 1더한다.

 

시간복잡도는 O(N log4(N))

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C1/%EC%BF%BC%EB%93%9C%EC%95%95%EC%B6%95%20%ED%9B%84%20%EA%B0%9C%EC%88%98%20%EC%84%B8%EA%B8%B0.cpp