[종만북] Divide & Conquer / 분할 정복

Algorithmic Problem Solving Strategies 

개인적으로 읽고 정리한 요약 입니다.

아래 링크에 문제 풀이 예제가 있습니다.

GitHub - chanheki/AlgorithmicProblemSolvingStrategies: Algorithm Book Study

분할 정복

도입

분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단하게 설명된다.

분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산.

분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것.

분할 정복을 사용하는 알고리즘들은 대개 세 가지의 구성 요소를 갖고 있다.

• 문제를 더 작은 문제로 분할하는 과정(divide)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)
• 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야하며, 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.

분할 정복의 장점은 많은 경우 같은 작업을 더 빠르게 처리해준다.

// 1부터 n까지의 합을 구하는 분할 정복 알고리즘
// 필수 조건: n은 자연수
// 1 + 2 + ... + n을 반환한다.
int fastSum(int n) {
    // base case
    if(n == 1) return 1;
    if(n % 2 == 1) return fastSum(n-1) + n;
    return 2*fastSum(n/2) + (n/2) * (n/2);
}

int sum(int n) {
    int ret = 0;
    for (int i = 1; i <= n; ++i)
        ret += i;
    return ret;
}

int recursiveSum(int n) {
    if(n == 1) return 1;
    return n + recursiveSum(n-1);
}

---

시간 복잡도 분석

recursiveSum()이 수행하는 데 걸리는 시간은 함수의 호출 횟수와 비례한다. n의 경우 n번의 함수 호출이 필요하다는 것을 알 수 있다.

그러나 fastSum()이 수행하는 데 걸리는 시간은 최소한 두번에 한번 꼴로 n이 절반으로 줄어든다. 그러므로 같은 n이더라도 fastSum이 더 빠르단 것을 알 수 있다.

fastSum(1011₂) = fastSum(1010₂) + 11
fastSum(1010₂) = fastSum(101₂) * 2 + 25
fastSum(101₂) = fastSum(100₂) + 5
fastSum(100₂) = fastSum(10₂) * 2 + 4
fastSum(10₂) = fastSum(1₂) * 2 + 1
fastSum(1₂)

재귀 호출을 할 때 n의 이진수 표현의 마지막 자리가 1이면 0으로 바뀌고, 마지막 자리가 0이면 끝자리가 없어진다는 것을 알 수 있다.

따라서 fastSum()의 총 호출 횟수는 n의 이진수 표현의 자릿수 + 첫자리를 제외하고 나타나는 1의 개수가 된다. 두 값의 상한은 모두 𝑙𝑜𝑔𝑵이므로 알고리즘의 실행 값은 O(𝑙𝑜𝑔𝑵)

수식으로 표현되지 않는 문제를 풀 때에 더욱 유용하게 사용된다. 그 좋은 예는 행렬의 거듭제곱.

n X n 크기의 행렬 A가 주어질 때, A의 거듭제곱(power) Aᴹ은 A를 연속해서 m번 곱한것.

행렬의 곱셈에는 O(n³)의 시간이 들기 때문에 m-1번의 곱셈을 통해 Aᴹ를 구하려면 모두 O(n³m)번의 연산이 필요.

n ≈ 100, m ≈ 1000000 정도 되면 연산의 수는 대략 1조로 추정. 이를 동기식으로 진행한다면 1초안에 계산하기는 힘들다. 그래서 사용하는 것이 분할정복.

Aᴹ을 구하는데 필요한 m개의 조각을 절반으로 나누면 이와 같이 표현 가능

Aᴹ = Aᴹ／² X Aᴹ／²

class SquareMatrix;

//n*n 크기의 항등 행렬(identity matrix)을 반환하는 함수
squareMatrix identity(int n);

//Aᴹ을 반환
squareMatrix pow(const SquareMatrix& A, int m) {
    // 기저사례 A⁰ = I
    if (m == 0) return identity(A.size());
    if (m % 2 > 0) return pow(A, m-1) * A;
    SquareMatrix half = pow(A, m/2);

    // Aᴹ = Aᴹ／² * Aᴹ／²
    return half * half
}

나누어 떨어지지 않을 때의 분할과 시간 복잡도

m이 홀수일 때, Aᴹ = A * Aᴹ⁻¹로 나누지 않고, 좀더 절반에 가깝게 나누는 것이 좋지 않을까 생각 할 수 있다. 예를 들어 A⁷ = A * A⁶ 이 아닌 A³ * A⁴로 나누는 것이 더 좋지 않은가 하는것. 실제로 문제의 크기가 매번 절반에 가깝게 줄어들면 기저 사례에 도달하기까지 걸리는 분할의 횟수가 줄어들기 때문에 대부분의 분할 정복 알고리즘은 가능한 절반에 가깝게 문제를 나누고자 한다. 퀵정렬의 경우도 마찬가지. 그러나 이 문제에서 이 방식의 분할은 오히려 알고리즘을 더 느리게 만든다. 이런 식으로 문제를 나누면 Aᴹ을 찾기 위해 계산해야 할 부분 문제의 수가 늘어나기 때문.

문제 간의 의존 관계도를 보여주는 그림.

pow(A, x)를 계산하는 과정에서 pow(A, y)를 호출해야 한다면 두 값은 화살표로 연결되어 있음.

얼핏보면 크게 차이나 보이지 않지만, 각 부분 문제가 계산되는 횟수가 다르다.
pow(A, 8)은 pow(A, 16)을 계산할 때도 호출되므로, 중복해서 호출된다. 다른 것들 또한 마찬가지로 결국 반으로 나누는 경우는 m - 1번 곱셈하는 것과 다를 바가 없어진다.

반면 다른 쪽은 pow()가 O(𝑙𝑜𝑔𝑵)개의 거듭제곱에 대해 한 번씩만 호출된다는 것을 쉽게 알 수 있다.

이 두 차이는 같은 문제를 어떻게 분할 하느냐에 따라 시간 복잡도 차이가 커진다는 것을 보여주는 좋은 예시가 된다.

절반으로 나누는 알고리즘이 큰 효율 저하를 불러오는 이유는 여러번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문. 이런 속성을 부분 문제가 중복된다 (overlapping subproblems)라고 부른다.

---

병합 정렬과 퀵정렬

이 두 알고리즘은 모두 분할 정복 패러다임을 기반으로 해서 만들어진 것들.

병합 정렬 알고리즘은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻는다.

반대로 퀵 정렬 알고리즘은 배열을 단순하게 가운데에서 쪼개는 대신, 병합 과정이 필요 없도록 한쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열을 분할.

이를 위해 퀵정렬은 파티션이라고 부르는 단계를 도입한다, 이는 배열에 있는 수 중 임의의 '기준 수(pivot)'를 지정한 후 기준보다 작거나 같은 숫자를 왼쪽, 더 큰 숫자를 오른쪽으로 보내는 과정

합병 정렬과 퀵정렬

병합 정렬은 각 수열의 크기가 1이 될 때까지 절반씩 쪼개 나간 뒤, 정렬된 부분 배열들을 합쳐 나가는 것을 볼 수 있다. 주어진 배열을 가운데서 절반으로 그냥 나눠 버리는 것.

이 과정을 상수 시간인 O(1)만에 수행할 수 있다.

그러나 각각 나눠서 정렬한 배열들을 하나의 배열로 합치기 위해 별도의 병합 과정을 실행 해야 한다. 그래서 여기서 O(n)의 시간이 걸린다.

이 두 알고리즘은 같은 아이디어로 정렬을 수행하지만 시간이 많이 걸리는 작업을 분할 단계에서 하느냐 아니면 병합 단계에서 하느냐 잘 보여주는 예시이다.

---

병합 정렬과 퀵정렬의 시간 복잡도 분석

병합 정렬은 conquer 되는 시간이 O(n)으로 일정하게 걸리고 divide 되는 시간이 거의 항상 절반으로 계속해서 줄어 O(𝑙𝑜𝑔n)이므로 병합 정렬의 시간 복잡도는 O(n𝑙𝑜𝑔n)이 된다.

퀵 정렬은 대부분의 시간을 차지하는 것은 주어진 문제를 두개의 부분 문제로 나누는 파티션 과정. 부분 문제가 비슷한 크기로 나눠진다는 보장을 할 수 없기 때문에 시간 복잡도 산출이 까다롭다. 최악의 경우에는 O(n²)가 되며 평균적으로 부분 문제가 절반에 가깝게 나눠진다면 병합정렬과 같은 O(n𝑙𝑜𝑔n)이 된다. 그래서 대부분의 퀵 정렬 구현은 가능한 절반에 가까운 분할을 얻기 위해 좋은 기준(pivot)을 뽑는 다양한 방법을 사용한다.

---

카라츠바의 빠른 곱셈 알고리즘

두 수를 각각 절반으로 쪼갠다. a와 b가 각각 256자리 수라면, a1과 b1은 첫 128자리, a0과 b0은 그 다음 128자리를 저장하도록 하는 것이다. 그러면 a와 b를 다음과 같이 나타낼 수 있다.

a = a₁ 𝖷 10¹²⁸ + a₀

b = b₁ 𝖷 10¹²⁸ + b₀

카라츠바는 이때 a 𝖷 b 를 네 개의 조각을 이용해 표현하는 방법을 살펴보았다. 예를 들면, 아래와 같이 표현할 수 있다.

a 𝖷 b = (a₁ 𝖷 10¹²⁸ + a₀) 𝖷 (b₁ 𝖷 10¹²⁸ + b₀) 

      = a₁𝖷b₁𝖷10²⁵⁶ + (a₁ 𝖷 b₀ + a₀ 𝖷 b₁) 𝖷 10¹²⁸ + a₀ 𝖷 b₀

이 방법에서는 큰 정수 두 개를 한 번 곱하는 대신, 절반 크기로 나눈 작은 조각을 네 번 곱한다. (10의 거듭제곱과 곱하는 것은 그냥 뒤에 0을 붙이는 시프트 연산으로 구현하면 되니 곱셈으로 치지 않는다.) 이대로도 각각을 재귀 호출해서 해결하면 분할 정복 알고리즘이라고 할 수 있다. 이 방법에서 길이 n인 두 정수를 곱하는데 드는 시간은 덧셈과 시프트 연산에 걸리는 시간 O(n)과 n/2 길이 조각들의 곱셈 네번으로 나눌 수 있다. 하지만, 이 방법의 전체 수행 시간이 O(n²)이 된다는 사실을 증명할 수 있다. 때문에 분할 정복을 구현한 의미가 없어진다.

카라츠바가 발견한 것은 다음과 같이 a 𝖷 b 를 포현했을 때 네 번 대신 세 번의 곱셈만으로만 이 값을 계산할 수 있다는 점이다.

a 𝖷 b = a₁ 𝖷 b₁ 𝖷 10²⁵⁶ + (a₁ 𝖷 b₀ + a₀ 𝖷 b₁) 𝖷 10¹²⁸ + a₀ 𝖷 b₀

각각의 부분을 아래와 같이 z₂, z₁, z₀이라고 쓴다.

우선 z₀와 z₂를 각각 한 번의 곱셈으로 구한다. 그리고 다음 식을 이용한다.

(a₀+a₁)⋅(b₀)+(b₁) = z₂: a₀ 𝖷 b₀
                    z₁: a₁ 𝖷 b₀ + a₀ 𝖷 b₁
                    z₀: a₁ 𝖷 b₁
                    =z₂ + z₁ + z₀

따라서 위 식의 결과에서 z₀과 z₂를 z₁을 구할 수 있다. 다음과 같은 코드 조각을 이용하면 된다.

z2 = a1 * b1
z0 = a0 * b0
z1 = (a0 + a1) * (b0 + b1) - z0 - z2

이 과정은 곱셈을 세 번밖에 쓰지 않는다. 이 세 결과를 다시 적절히 조합해 원래 두 수의 답을 구해낼 수 있다. 아래는 이와 같이 구현한 카라츠바 알고리즘의 구현을 swifty에 가깝게 작성한 코드이다.

// O(n^2)
// Long Multiplication
func multiply(_ num1: Int, by num2: Int, base: Int = 10) -> Int {
  let num1Array = String(num1).characters.reversed().map{ Int(String($0))! }
  let num2Array = String(num2).characters.reversed().map{ Int(String($0))! }

  var product = Array(repeating: 0, count: num1Array.count + num2Array.count)

  for i in num1Array.indices {
    var carry = 0
    for j in num2Array.indices {
      product[i + j] += carry + num1Array[i] * num2Array[j]
      carry = product[i + j] / base
      product[i + j] %= base
    }
    product[i + num2Array.count] += carry
  }

  return Int(product.reversed().map{ String($0) }.reduce("", +))!
}

// O(nᴸᵍ³)
// Karatsuba Multiplication
func karatsuba(_ num1: Int, by num2: Int) -> Int {
  let num1Array = String(num1).characters
  let num2Array = String(num2).characters

  guard num1Array.count > 1 && num2Array.count > 1 else {
    return num1*num2
  }

  let n = max(num1Array.count, num2Array.count)
  let nBy2 = n / 2

  let a = num1 / 10^^nBy2
  let b = num1 % 10^^nBy2
  let c = num2 / 10^^nBy2
  let d = num2 % 10^^nBy2

  let ac = karatsuba(a, by: c)
  let bd = karatsuba(b, by: d)
  let adPlusbc = karatsuba(a+b, by: c+d) - ac - bd

  let product = ac * 10^^(2 * nBy2) + adPlusbc * 10^^nBy2 + bd

  return product
}

---