[ 알고리즘 ] 분할 정복 알고리즘(Divide and conquer algorithm)

 

분할 정복 알고리즘이란?

등차수열의 공식과 연관지어 생각해본다!

분할 정복 알고리즘은 문제를 나눌 수 없을 때 까지 작게 나누어서(Divide) 각각을 해결하여 정복(Conquer)하는 알고리즘이다.

 

-이처럼, 분할 정복은 하위 문제를 재귀적으로 해결하기 때문에 하위 문제 각각은 원래 문제보다 범위가 작아야 하며 하위 문제는 각 문제마다 탈출 조건이 존재해야 합니다.

---

분할정복 알고리즘 설계 요령

(1) Divide : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다.-> 이 과정이 가장 중요한 과정.

 

(2) Conquer : 나누어진 하위 문제를 재귀적으로 해결한다. 즉 하위 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 탈출 조건으로 놓고 해결한다.

 

(3) Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

 

---

분할정복 알고리즘의 장단점

 

장점: 문제를 나눔으로써 어려운 문제를 해결할 수 있다는 엄청나게 중요한 장점이 있다. 그리고 이 방식이 그대로 사용되는 효율적인 알고리즘들도 여럿 있으며, 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.

 

단점: 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점

 

---

+) 병합정렬 (Merge Sort)

선택, 삽입, 버블 정렬의 시간 복잡도는 Θ(n2)이다. 분할정복법을 활용하면 이 시간복잡도를 O(n log n)까지 줄일 수 있다.

 

병합 정렬의 과정

-> 궁극적인 목표: 전체 배열 정리, 하위 문제: 하위 배열(array[p…r]) 정렬

 

1. 분할: p와 r의 중간 q 를 찾는다. 이진 검색에서 중간점을 찾았던 것과 같이 이 과정을 수행한다. p와 r을 더해서 2로 나눈 후 내림을 하여 정수로 만든다.

 

2. 정복: 분할 단계 에서 만들어진 두 하위 문제 각각에 있는 하위 배열을 재귀적으로 정렬한다. 즉, 하위 배열 array[p..q]를 재귀적으로 정렬하고 또 하위 배열 array[q+1..r]을 재귀적으로 정렬한다.

 

3. 결합: 정렬된 두 하위 배열을 하나의 정렬된 하위 배열인 array[p…r]로 결합한다.

 

병합 정렬에는 2개의 함수를 필요로 한다

- MERGE-SORT : 구간을 둘로 쪼개고 MERGE를 호출한다.

- MERGE : 두 개의 정렬된 배열을 하나로 합친다.

 

두 데이터 집합을 정렬하면서 합치는 방법

1. 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합을 만든다.

2. 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 빈 데이터 집합에 추가한다. 그리고 새 데이터 집합에 추가한 요소는 원래 데이터 집합에서 삭제한다.

3. 원래 두 데이터 집합의 요소가 모두 삭제될 때 까지 2를 반복한다.

 

Pseudo Code

A : 정렬하고자 하는 배열[]

p : 구간의 제일 왼쪽 index

q : 구간의 중간 index

r : 구간의 제일 오른쪽 index

 

 

---

분할 정복 적용 문제

 

https://www.acmicpc.net/problem/1992

<백준1992번 쿼드트리>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//쿼드트리//

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] img = new int[n][n];
        for (int i = 0; i < n; i++) {
            String readLine = br.readLine();
            for (int j = 0; j < n; j++) {
                img[i][j] = readLine.charAt(j) - '0';
            }
        }

        StringBuilder sb = new StringBuilder();
        dfs(sb, img, 0, 0, n);

        System.out.println(sb.toString());
    }

    private static void dfs(StringBuilder sb, int[][] img, int startY, int startX, int n) {
        boolean check = canCompress(img, startX, startY, n);

        if (check) {
            sb.append(img[startY][startX]);
        } else {
            sb.append("(");
            dfs(sb, img, startY, startX, n / 2);
            dfs(sb, img, startY, startX + n / 2, n / 2);
            dfs(sb, img, startY + n / 2, startX, n / 2);
            dfs(sb, img, startY + n / 2, startX + n / 2, n / 2);
            sb.append(")");
        }
    }

    private static boolean canCompress(int[][] img, int startX, int startY, int n) {
        int value = img[startY][startX];
        for (int i = startY; i < startY + n; i++) {
            for (int j = startX; j < startX + n; j++) {
                if (value != img[i][j]) return false;
            }
        }
        return true;
    }
}

 

 

---

 

풀어볼 문제

 

풀어볼 

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

https://www.acmicpc.net/problem/2448

2448번: 별 찍기 - 11