분할 정복

분할 정복 기법

유래

• 1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략
• 전략이 우세한 연합군을 공격하기 위해 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나눔
• 둘로 나뉜 연합군을 한 부분씩 격파함

설계 전략

• 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
• 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
• 통합(Combine) : (필요하다면) 해결된 해답을 모은다.

Top-down approach

거듭 제곱

반복(iterative) 알고리즘: O(n)

분할 정복 기반의 알고리즘: O(log n)

분할 정복 응용 - 같은 색 공간 만들기

• 여러 개의 작은 단위 정사각형(크기 1) 공간들로 이루어진 커다란 정사각형 모양의 공간이 주어져 있고, 각 단위 정사각형 공간들은 하얀색 또는 초록색으로 칠해져 있다.

• 주어진 정사각형 공간을 일정한 규칙에 따라 나누어 다양한 크기를 갖는 정사각형 모양의 하얀색 또는 초록색의 공간으로 만들려고 한다.

• 입력으로 주어진 전체 공간의 한변의 길이 N과 전체 공간을 구성하는 각 단위 정사각형 공간의 색상(하얀색 또는 초록색)이 주어질 때 규칙에 따라 나누어진 하얀색 공간과 초록색 공간의 정사각형의 개수를 구하는 프로그램을 작성하시오.
  

• 규칙

1. 전체 공간의 크기는 NxN(N = 2, 4, 8, 16, 32, 64, 128 중 하나)
2. 공간이 모두 같은 색으로 칠해져 있지 않으며, 가로와 세로로 중간 부분을 잘라서 똑같은 크기의 네 개의 N/2 x N/2 공간으로 나눈다.
3. 나누어지 네 개의 공간 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 공간으로 나눈다.
4. 이와 같은 과정을 나누어진 공간이 모두 하얀색 또는 모두 초록색으로 칠해져 있거나, 하나의 정사각형 공간이 되어 더 이상 나눌 수 없을 때까지 반복한다.
   

구현 코드

import java.util.Scanner;

/**
 입력
 8
 1 1 0 0 0 0 1 1
 1 1 0 0 0 0 1 1
 0 0 0 0 1 1 0 0
 0 0 0 0 1 1 0 0
 1 0 0 0 1 1 1 1
 0 1 0 0 1 1 1 1
 0 0 1 1 1 1 1 1
 0 0 1 1 1 1 1 1
 */

/**
 출력
 9
 7
 */
public class DivideSpaceTest {
    static int N, map[][], white, green;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        cut(0, 0, N);
        System.out.println(white);
        System.out.println(green);
    }
    static void cut(int y, int x, int size){

        int sum = 0;
        for (int i = y, yEnd = y + size; i < yEnd; i++) {
            for (int j = x, xEnd = x + size; j < xEnd; j++) {
                sum += map[i][j];
            }
        }

        if(sum == 0){
            ++white;
        } else if (sum == size * size) {
            ++green;
        } else {
            int half = size/2;
            cut(y, x, half);
            cut(y, x + half, half);
            cut(y + half, x, half);
            cut(y + half, x + half, half);
        }
    }
}