분할 정복

분할 정복

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다.

대표적 예는 정렬 알고리즘 중에서 퀵, 합병 정렬과 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제가 대표적입니다.

 

분할정복법의 설계전략?

1. 분할 : 문제 사례를 하나 이상의 작은 사례로 분할(Divide) 합니다.
2. 정복 : 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 재귀를 사용합니다.
3. 병합 : 필요하다면, 작은 사례에 대한 해답을 통한(Combine)하여 원래 사례의 해답을 구합니다.

분할정복법의 장단점?

장점

• Top-down 재귀 방식으로 구현하기 때문에 코드가 직관적입니다.
• 문제를 나누어 해결한다는 특징 상 병렬적으로 문제를 해결

단점

• 재귀 함수 호출로 오버헤드가 발생할 수 있습니다.
• 스택에 다량의 데이터가 보관되는 경우, 오버플로우가 발생

 

분할 정복과 동적 계획법의 차이는?

둘 다 쪼개서 작은 단위로 분할하여 문제를 해결하는 건 비슷한 알고리즘입니다.

그래도 차이가 있습니다.

동적 계획법(DP)은 작은 단위로 쪼갠 문제가 이후에도 중복되어 발생하기 때문에 결과를 저장해두고,

상위 문제를 해결하기 위해서 재활용 됩니다.

반대로,

분할 정복은 하위 문제들이 중복되지 않기 때문에 재활용되거나 그렇지는 않습니다.

 

---

 

 

분할 정복 알고리즘으로 푼 문제로 코드로 설명을 추가로 하겠습니다.

종이의 개수

1780번: 종이의 개수

 

위 백준 문제는 분할정복을 할 때,

9방면으로 분할하여 재귀호출을 한 뒤에 원하는 조건에 맞으면 count(정복)를 해주어 최종적으로 map 자료구조를 이용(병합)하여 담긴 count 최종 값을 출력해주는 방식으로 로직을 설계했습니다.

 

아래는 구현한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Boj_종이의개수 {
    static int[][] board;
    static Map<Integer, Integer> result = new HashMap<>(3);

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        board = new int[N][N];

        // input settings
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++)
                board[i][j] = Integer.parseInt(st.nextToken());
        }

        recursiveBoard(N, 0, 0);

        int[] printData = new int[3];
        for (int key : result.keySet()) {
            if (key == -1) printData[0] = result.get(key);
            else if (key == 0) printData[1] = result.get(key);
            else printData[2] = result.get(key);
        }

        for (int i : printData) {
            System.out.println(i);
        }
    }

    private static void recursiveBoard(int N, int row, int col) {
        int target = board[row][col];

        for (int i = row; i < row + N; i++) {
            for (int j = col; j < col + N; j++) {
                if (board[i][j] != target) {
                    int nN = N / 3;
                    int nRow = (row / 3) * 3;
                    int nCol = (col / 3) * 3;
                    
                    // 9곳을 recur 다 돌리기..
                    /**
                     * N = 27 일 경우
                     * 0,0  0,9  0,18
                     * 9,0  9,9  9,18
                     * 18,0 18,9 18,18
                     */
                    recursiveBoard(nN , nRow + nN * 0, nCol + nN * 0);
                    recursiveBoard(nN , nRow + nN * 0, nCol + nN * 1);
                    recursiveBoard(nN , nRow + nN * 0, nCol + nN * 2);

                    recursiveBoard(nN , nRow + nN * 1, nCol + nN * 0);
                    recursiveBoard(nN , nRow + nN * 1, nCol + nN * 1);
                    recursiveBoard(nN , nRow + nN * 1, nCol + nN * 2);

                    recursiveBoard(nN , nRow + nN * 2, nCol + nN * 0);
                    recursiveBoard(nN , nRow + nN * 2, nCol + nN * 1);
                    recursiveBoard(nN , nRow + nN * 2, nCol + nN * 2);
                    return;
                }
            }
        }
        // 통과 됐다는 건? 다 동일하다는 뜻
        result.put(target, result.getOrDefault(target, 0) + 1);
    }
}