분할 정복

• 문제를 분할한다.
• 분할된 문제를 전체 문제와 같은 logic으로 처리한다.
  근데이제 크기가 작은
• 문제를 쪼개 subproblem에 대한 해를 구한다
  → 또귀호출
• 근데 분할했다고 모든 subproblem에 대해 해를 구할 필요는 없다.
  (필요 없음이 분명하면 안 해봐도 됨)

Ex)

• Merge sort
• Binary search

같은 색 공간 만들기

1. 전체 공간의 크기는 $N \times N$, $N=2^k\;s.t.\;k\in\N$
2. 공간이 모두 같은 색이 아니라면 가로와 세로를 반으로 나눈다.
   즉 총 4개의 $\displaystyle{\frac{N}{2} \times \frac{N}{2}}$ 공간으로 나뉜다.
3. 나눠진 각 $\displaystyle{\frac{N}{2} \times \frac{N}{2}}$의 공간에 대해서도 2.을 반복한다.
4. 3.을 다음의 두 조건 중 하나를 만족할 때까지 반복한다.
   • 나눠진 공간이 모두 하얀색 또는 초록색으로 칠해져 있다.
   • 나눠진 공간이 $1 \times 1$이 되어 더이상 나눌 수 없다.

import java.util.*;

public class MakeSpaceTest {
    static int white = 0;
    static int green = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[][] spaces = new int[n][n];
        for(int r = 0; r < n; ++r) {
            for(int c = 0; c < n; ++c) {
                spaces[r][c] = sc.nextInt();
            }
        }

        makeSpace(spaces, 0, 0, n);
        System.out.println(white);
        System.out.println(green);

        sc.close();
    }

    private static void makeSpace(int[][] spaces, int r, int c, int size) {
        //영역의 좌상단 위치, 영역 크기
        int sum = 0;
        for(int i = r; i < r + size; ++i) {
            for(int j = c; j < c + size; ++j) {
                sum += spaces[i][j];
            }
        }

        //처음 두 조건이 base case가 된다.
        //즉 size == 1을 체크할 필요가 없다.
        if(sum == 0) { //모든 칸이 0인 경우
            ++white;
        } else if(sum == size*size) { //모든 칸이 1인 경우
            ++green;
        } else {
            int halfSize = size/2;
            makeSpace(spaces, r, c, halfSize);
            makeSpace(spaces, r + halfSize, c, halfSize);
            makeSpace(spaces, r, c + halfSize, halfSize);
            makeSpace(spaces, r + halfSize, c + halfSize, halfSize);
        }
    }

}

이진 탐색

• 일단 정렬이 되어 있어야 성립한다.

binarySearch(s[], n, key)

Arrays.binarySearch

import java.util.*;

public class ArraysBinarySearchExample {
    public static void main(String[] args) {
        int[] a = new int[] {1, 3, 5, 7, 9};
		
        for(int i = 0; i <= 20; i += 2) {
            System.out.println(Arrays.binarySearch(a, i));
        }
    }
}

-1
-2
-3
-4
-5
-6
-6
-6
-6
-6
-6

주어진 배열에 key가 존재하면 key의 index가 반환되고, 그렇지 않으면 음수가 반환된다.
이 음수 값은 절대값을 취하면 해당 원소가 삽입되어야 할 위치의 인덱스가 된다.