알고리즘 - 분할정복

분할정복

---

분할 정복은 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 해결한 뒤 결과를 결합하여 원래 문제의 해를 구하는 알고리즘 설계 기법이다.

이 방법은 재귀적 접근을 기반으로 하며, 특정 문제를 풀기 위해 문제를 반복적으로 쪼개어 더 단순한 형태로 만들고 이를 조합하여 해를 도출한다. 이 과정은 아래 세 단계로 구성된다:

1. 분할(Divide):
   • 원래 문제를 더 작은 부분 문제로 분할한다.
   • 일반적으로 이 단계는 입력 데이터를 나누거나, 문제의 범위를 축소하는 과정을 포함한다.
2. 정복(Conquer):
   • 나뉜 부분 문제를 재귀적으로 해결한다.
   • 하위 문제의 크기가 충분히 작아지면(예: 크기가 1인 경우), 직접 해결(기저 사례)한다.
3. 결합(Combine):
   • 각 부분 문제의 결과를 결합하여 원래 문제의 해를 구한다.
   • 결합 과정은 문제의 성격에 따라 다양하며, 예를 들어 정렬, 덧셈, 병합 등이 포함될 수 있다.

특징

 

• 재귀적 설계: 대부분의 분할 정복 알고리즘은 재귀적으로 구현된다.
• 독립성: 하위 문제들이 서로 독립적이므로 병렬 처리에 유리하다.
• 효율성: 문제를 나눔으로써 해결 과정을 간소화하며, 일부 문제에 대해 시간 복잡도를 대폭 낮출 수 있다.

 

분할정복 예시

---

2630번 문제 기준

 

public class Main {
    static int white, blue = 0;
    static int[][] arr;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
        divide(0, 0, N);
        bw.write(white + "\n" + blue);
        bw.flush();
        bw.close();
        br.close();
    }
    public static void divide(int x, int y, int size){
        int sum = 0;
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                sum += arr[i][j];
            }
        }
        if (sum == 0) {
            white++;
        } else if (sum == size * size) {
            blue++;
        } else {
            divide(x, y, size / 2);
            divide(x + size / 2, y, size / 2);
            divide(x, y + size / 2, size / 2);
            divide(x + size / 2, y + size / 2, size / 2);
        }
    }
}

 

 

 

1. 입력 및 초기화

• N: 행렬의 크기. 행렬은 N x N 크기의 정사각형.
• arr: 행렬을 저장하는 2차원 배열. 값은 0(흰색) 또는 1(파란색).

2. 분할 로직

메인 로직은 divide(x, y, size) 함수에 있습니다.

• (x, y)는 현재 확인 중인 부분 행렬의 좌측 상단 좌표.
• size는 현재 부분 행렬의 크기.
• 부분 행렬의 모든 원소의 합을 계산하여 다음을 수행:
  1. 합이 0이면 해당 부분은 모두 흰색(white++).
  2. 합이 size * size이면 모두 파란색(blue++).
  3. 그 외의 경우, 부분 행렬을 4등분하여 재귀적으로 나눔.

3. 출력

최종적으로 white와 blue의 값을 출력하여 하얀색과 파란색 종이의 개수를 나타냄.