알고리즘 - 분할정복법 (Divide and Conquer)

분할정복법 (Divide and Conquer)이란?

분할정복법은 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복 (Conquer)하는 방법이다.
분할정복법은 문제의 사례를 2개 이상의 더 작은 사례로 나눈다. 이 작은 사례는 주로 원래 문제에서 따온다. 나눈 작은 사례의 해답을 바로 얻을 수 있으면 해를 구하고 아니면  더 작은 사례로 나눈다.
해를 구할 수 있을 만큼 충분히 더 작은 사례로 나누어 해결하는 방법이다.
분할 정복법은 하향식(top-down) 접근 방법으로 최상위 사례의 해답은 아래로 내려가면서 작은 사례에 대한 해답을 구함으로써 구한다.

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

분할정복법이 쓰이는 예는 이분검색, 합병정렬, 퀵정렬, 최대값 찾기, 임계값의 결정, 쉬트라센 행렬곱셈 알고리즘 등이 있다.

분할정복법의 장단점

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

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

이분검색

10개의 정렬된 배열에서 값을 21가진 인덱스 찾기

low: 0
high: 9
middle: (low + high)/2 => 4.5 => 4

low: 4 + 1 => 5
high: 9
middle: 7

low: 5
high: 7 - 1 = 6
middle: 5

low: 5 + 1 = 6
high: 6

int[] arr = {5, 7, 10, 12, 16, 20, 21, 25, 28, 30} public int binarySearch(int target) { low = 0; high = arr.length; while (low <= high) { middle = (low + high) / 2; if (target == array[middle]) { return middle; } else if (target > array[middle]) { low = middle + 1; } else { high = middle - 1; } } return -1; //not found }

최대값 찾기

8개의 배열에서 값을 최대값 찾기

int arr[] = {6, 2, 9, 8, 1, 4, 17, 5}; public int max(int[] arr, int low, int high) { int m, left, right; m = (low + high) / 2; if(low == high) return arr[low]; left = max(arr, low, m); right = max(arr, m + 1, high); return (left > right)?left:right; }

문제풀이

https://www.algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

www.algospot.com

풀이

테스트 케이스: xbwxwbbwb
변환 후: xxbwwbbbw

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static String reverseQuadTree(String str) { char firstChar = str.charAt(0); if (firstChar != 'x') return String.valueOf(firstChar); int index = 1; //첫 문자 x를 제외하기 위해 //4등분시 왼쪽 위 조각 String leftTop = reverseQuadTree(str.substring(index)); //4등분시 오른쪽 위 조각 index += leftTop.length(); String rightTop = reverseQuadTree(str.substring(index)); //4등분시 왼쪽 아래 조각 index += rightTop.length(); String leftBottom = reverseQuadTree(str.substring(index)); //4등분시 오른쪽 아래 조각 index += leftBottom.length(); String rightBottom = reverseQuadTree(str.substring(index)); return "x" + leftBottom + rightBottom + leftTop + rightTop; } public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int C = Integer.parseInt(br.readLine().trim()); for (int i = 0; i < C; i++) { String testCase = br.readLine(); System.out.println(reverseQuadTree(testCase)); } } }