10. Divide and Conquer(분할정복)

Divide and Conquer(분할정복)

정의

• 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 직접 풀 수 있는 문제가 간단해질 때까지 재귀적으로 분할하고 부속문제들의 해답들이 다시 합쳐서 해결하자는 개념

• 문제를 더 이상 나눌 수 없을 때까지 나눈 후 문제들을 해결하며 병합하여 결과 값을 얻는 알고리즘

• 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀호출을 이용해 계산하고, 각 부분문제의 답으로 부터 전체 문제의 답을 계산해내는 것.

예를 들어 정렬할 배열 [5, 2, 4, 1]을 [5,2]와 [4,1]로 나누어 각각 정렬하면 [2,5], [1,4]가 된다. 두 결과의 앞 원소를 비교하며 합치면 [1,2,4,5]가 된다. 여기서 분할, 작은 문제를 푸는 기저 사례, 결합이 모두 필요하다. 작은 문제의 답을 여러 경로에서 되풀이한다면 동적 계획법처럼 저장할 수 있는지도 검토한다.

알고리즘 설계 방법

(1) Divide(분할) : 문제가 분할이 가능한 경우, 2개 이상 하위 문제로 나눈다. (2) Recursion(재귀) : 재귀적으로 부속문제들을 푼다. (3) Conquer(정복) : 해답들을 적절하게 합친다.

1. Divide(분할) : 문제를 더 작은 문제로 분할하는 과정 (문제가 분할이 가능한 경우, 2개 이상 하위 문제로 나눔)

2. Recursion(재귀) : 재귀적으로 부속문제들을 푼다. (더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은문제 Base Case에 도달 할 때까지)

3. Conquer(정복[Merge]) : 해답들을 적절하게 합친다.(각 문제에 대한 답을 원래 문제에 대한 답으로 병합하는 과정)

중요사항

• 문제를 잘 나누는 것

• 문제를 잘 합치는 것

• 분할 정복 기법에서는 재귀를 이용하여 비슷한 종류의 부속 문제들을 해결

장점

• 어려운 문제를 해결한다.(하노이탑 등)

• 병렬화(Parallelism) : 프로세스 시스템

• 메모리접근(Memory Access) : 캐시의 효율성

단점

• 재귀 호출에는 스택과 호출 비용이 든다. 다만 전체 비용은 분할과 결합 비용에 따라 결정되므로 재귀라는 이유만으로 항상 느린 것은 아니다.

• 재귀를 저장하기 위해 스택이 필요.

• 어떤 문제들 에서는 반복 방법보다 더 복잡할 수 있다.

Merge Sort

분할(devied)

1. 정렬할 데이터 집합을 반으로 나눈다.

2. 나누어진 하위데이터 집합의 크기가 2 이상이면 하위 데이터 집합에 대해 (1.)을 반복

3. 원래 같은 집합에서 나누어진 하위 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. (병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬)

4. 데이터 집합이 다시 하나가 될 때까지 (3.)을 반복

병합(combine)

1. 두 데이터의 집합을 합한 것 만큼 비어 있는 데이터 집합을 마련

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

3. 양쪽 데이터 집합이 빌 때까지 (2.) 의 과정을 반복

구현

아래 mergeSort(data, startIdx, endIdx)의 구간은 양 끝을 포함한다. 길이가 0 또는 1이면 이미 정렬돼 있으므로 바로 돌아간다. 재귀가 끝난 시점에는 왼쪽 [startIdx..midIdx]와 오른쪽 [midIdx+1..endIdx]가 각각 정렬돼 있다는 불변식이 성립한다. combine은 두 구간의 앞 원소 중 작은 값을 새 배열에 옮기므로 전체 정렬을 유지한다.

MergeSort

/**
 * 1. 데이터를 나눌 수 있는지 확인
 * 2. 중간 값 계산
 * 3. 오른쪽 분할
 * 4. 왼쪽 분할
 * 5. 결합
 *
 * @param data
 * @param startIdx
 * @param endIdx
 */
public static void mergeSort(int[] data, int startIdx, int endIdx) {
  int midIdx = 0;
  if (endIdx - startIdx < 1) {
    return;
  }
  midIdx = startIdx + (endIdx - startIdx) / 2;
  mergeSort(data, startIdx, midIdx);
  mergeSort(data, midIdx + 1, endIdx);
  combine(data, startIdx, midIdx, endIdx);
}

Combine

    /**
     * 데이터 결합
     *
     * 1. 데이터 비교 후 정렬
     * 2. 남은 데이터 정렬
     *
     * @param data
     * @param startIdx
     * @param midIdx
     * @param endIdx
     */
    private static void combine(int[] data, int startIdx, int midIdx, int endIdx) {
        int[] destData = new int[(endIdx - startIdx) + 1];
        int rightIdx = midIdx + 1;
        int leftIdx = startIdx;
        int destIdx = 0;

        while (leftIdx <= midIdx && rightIdx <= endIdx) {
            if (data[leftIdx] <= data[rightIdx]) {
                destData[destIdx] = data[leftIdx];
                leftIdx++;
            } else {
                destData[destIdx] = data[rightIdx];
                rightIdx++;
            }
            destIdx++;
        }
        while (leftIdx <= midIdx) {
            destData[destIdx++] = data[leftIdx++];
        }

        while (rightIdx <= endIdx) {
            destData[destIdx++] = data[rightIdx++];
        }
        destIdx = 0;
        for (int i = startIdx; i <= endIdx; i++) {
            data[i] = destData[destIdx++];
        }
    }

같은 값이 양쪽에 있다면 <=로 왼쪽 원소를 먼저 선택해 원래 순서를 보존한다. 이 성질이 안정 정렬이다. 기존 <는 같은 값에서 오른쪽을 먼저 옮겨 안정성을 잃었다. 배열을 매번 반으로 나누면 재귀 깊이는 O(log N), 각 깊이에서 모든 원소를 한 번 병합하므로 T(N)=2T(N/2)+O(N)=O(N log N)이다. 병합용 배열의 최대 총 크기는 한 깊이에서 O(N)이고 재귀 스택은 O(log N)이다. 여기서는 호출마다 임시 배열을 새로 만들지만 한 번만 할당해 재사용할 수도 있다.

거듭제곱

Sequence

public static long power(int base, int exp) {
  if (exp < 0) throw new IllegalArgumentException("음수 지수는 정수 결과로 표현하지 않습니다");
  long result = 1;
  for(int i=0; i<exp; i++) {
    result *= base;
  }
  return result;
}

Recursion

/**
 * C(n) = C^n/2 C^n/2 (even)
 * C(n) = C^(n-1)/2 C^(n-1)/2 * C(odd)
 * exp == 1=> base
 * exp == 0 => 1
 * @param base
 * @param exp
 * @return
 */
public static long power1(int base, int exp) {
  if (exp < 0) throw new IllegalArgumentException("음수 지수는 정수 결과로 표현하지 않습니다");
  if (exp == 1) {
    return base;
  } else if (exp == 0) {
    return 1;
  }

  if (exp % 2 == 0) {
    long newBase = power1(base, exp/2);
    return newBase * newBase;
  } else {
    long newBase = power1(base, (exp-1)/2);
    return (newBase * newBase) * base;
  }
}

power1(2, 13)은 지수 13을 6, 3, 1로 절반씩 줄인다. 돌아오면서 2¹ → 2³ → 2⁶ → 2¹³을 만든다. 각 단계에서 재귀 호출을 한 번만 하고 그 결과를 제곱하므로 T(e)=T(e/2)+O(1)=O(log e)다. 같은 함수를 두 번 호출해 각각의 절반을 다시 계산하면 장점이 사라진다. 반복 곱셈 power는 O(e)다. 0 지수는 1로 처리하고 음수 지수는 이 정수 반환형의 범위 밖이다. 큰 지수는 long에서도 오버플로가 나므로 정확한 큰 수 계산에는 BigInteger를 사용한다.

피보나치 수

F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2)

/**
 * F(0) = 0
 * F(1) = F(2)= 1
 * F(n) = F(n-1) + F(n-2)
 * @param n
 * @return
 */
public static long fibonacci(int n) {
  if (n < 0) throw new IllegalArgumentException("n은 0 이상이어야 합니다");
  if (n == 0) {
    return 0;
  } else if (n == 1 || n == 2) {
    return 1;
  }
  return fibonacci(n-1) + fibonacci(n-2);
}

이 단순 재귀는 F(n-2) 같은 값을 여러 경로에서 반복 계산하므로 호출 수가 지수적으로 증가한다. 피보나치 재귀를 분할 정복이면 무조건 빠르다는 예로 받아들이면 안 된다. 중복 상태를 저장하는 동적 계획법은 O(n)이고, 다음 행렬 제곱은 O(log n)번의 2×2 행렬 곱셈으로 구할 수 있다.

2x2 행렬 피보나치 수열 찾기

public static long fibonacciMatrix(int n) {
  if (n < 0) throw new IllegalArgumentException("n은 0 이상이어야 합니다");
  if (n == 0) return 0;
  long[][] matrix2x2 = new long[2][2];
  matrix2x2[0][0] = 1;
  matrix2x2[0][1] = 1;
  matrix2x2[1][0] = 1;
  matrix2x2[1][1] = 0;

  matrix2x2 = matrix2x2_Power(matrix2x2, n);
  return matrix2x2[0][1];
}

private static long[][]  matrix2x2_Power(long[][] matrixA, int n) {
  if (n > 1) {
    matrixA = matrix2x2_Power(matrixA, n /2);
    matrixA = matrix2x2_multiply(matrixA, matrixA);
    if ((n & 1)  == 1) {
      long[][] matrixB = new long[2][2];
      matrixB[0][0] = 1;
      matrixB[0][1] = 1;
      matrixB[1][0] = 1;
      matrixB[1][1] = 0;
      matrixA = matrix2x2_multiply(matrixA, matrixB);
    }
  }
  return matrixA;
}

private static long[][] matrix2x2_multiply(long[][] matrixA, long[][] matrixB) {
  long[][] result = new long[2][2];
  result[0][0] = matrixA[0][0] * matrixB[0][0] + matrixA[0][1] * matrixB[1][0];
  result[0][1] = matrixA[0][0] * matrixB[0][1] + matrixA[0][1] * matrixB[1][1];
  result[1][0] = matrixA[1][0] * matrixB[0][0] + matrixA[1][1] * matrixB[1][0];
  result[1][1] = matrixA[1][0] * matrixB[0][1] + matrixA[1][1] * matrixB[1][1];
  return result;
}

행렬 $Q=\begin{bmatrix}1&1\\1&0\end{bmatrix}$에 대해 $Q^n$의 오른쪽 위 칸이 $F(n)$이다. 코드의 matrix2x2_Power는 지수를 절반으로 줄여 같은 중간 행렬을 한 번 계산한 다음 제곱한다. 홀수라면 기본 행렬 $Q$를 한 번 더 곱한다. n=0에서는 항등 행렬이 필요하므로 위 호출자는 바로 0을 반환하도록 했다. 행렬 곱셈 한 번이 고정 크기에서는 O(1)이므로 전체 시간과 재귀 스택은 O(log n)이다. 여기서도 long 오버플로가 가능하며, n > 92의 정확한 피보나치 수에는 더 큰 정수 타입이 필요하다.

Divide And Conquer(분할정복)