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

  분할 정복(Divide and Conquer)이란 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘입니다. 예를 들어 합병 정렬, 퀵 정렬, 이진 검색 등이 있습니다.

 분할 정복은 세 가지 과정으로 이루어집니다. 문제를 하나 이상의 작은 부분들로 '분할'하고, 부분 문제를 해결하여 '정복'하고, 부분에서 해결한 문제를 '조합'하여 원래 문제의 답을 구하는 것입니다. 이는 재귀함수를 이용하여 구현할 수 있습니다.

  문제를 나누어서 처리하기 때문에 어려운 문제도 해결할 수 있고, 병렬 처리에 이점이 있다는 장점이 두드러집니다. 그러나 재귀 호출 구조를 이용하기 때문에 잦은 분할 시에는 메모리를 많이 사용하거나 동작이 느려질 수 있다는 단점이 있습니다.

 

  분할 정복 구현 코드(최댓값 찾기)

public static int getMax(int[] array, int left, int right) {
    int mid = (left + right) / 2;
    if (left == right) {
      return array[left];
    }
    left = getMax(array, left, mid);
    right = getMax(array, mid + 1, right);
    return (left > right) ? left : right;
}

  매개 변수로 배열 array와 정수형 left와 right를 받는 getMax 메소드를 생성합니다.

  분할 기준이 되는 변수 mid를 생성합니다. left와 right를 더한 값에 2로 나눈 값을 할당합니다.

  if문에서 left와 right가 동일하다면 array의 left 번째 원소를 반환합니다. 인덱스가 같은 것이므로 left든 right든 동일한 원소를 가리키고 있을 것입니다.

  left에 getMax를 호출하고 인자에 array, left, right를 넣습니다. 배열을 left에서 mid까지 분할합니다.

  right에 getMax를 호출하고 인자에 array, left, right를 넣습니다. 배열을 mid + 1에서 right까지 분할합니다.

  삼항 연산자를 이용하여 left가 right보다 크다면 left를, 그렇지 않다면 right를 반환합니다.