4. Divide-and-Conquer

분할 정복 문제는 다음과 같이 푼다.

  • 문제를 똑같은 부분 문제들로 나눈다.
  • 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 작다면 간단한 방법으로 푼다.
  • 부분 문제의 해법을 병합해 원본 문제의 해법으로 만든다.

재귀적으로 푸는 부분 문제들을 재귀 케이스라고 하며, 간단한 방법으로 푸는 작은 부분 문제들을 기본 케이스라고 한다.

Recurrences

재귀식은 함수가 더 작은 입력을 받는 그 자신을 포함하는 등식이나 부등식을 말한다. 부분 문제들이 기본 문제의 상수배만큼 작을 필요는 없다. 재귀식을 푸는 데는 3가지 방법이 존재한다.

  • 대입법에서는 상한을 예상하고 수학적 귀납법으로 추측을 증명한다.
  • 재귀 트리법에서는 각각의 노드가 수행 시간을 나타내는 트리로 재귀를 표현한다.
  • 마스터 방법에서는 T(n) = aT(n/b) + f(n) 식의 재귀식에 대한 상한을 계산한다.

Technicalities in recurrences

병합 정렬의 재귀식은 엄밀히는 n > 1에서 T(n) = T(\lfloor (n/2) \rfloor) + T(\lceil n/2 \rceil) + \Theta(n)이지만, 이런 디테일은 무시하고 T(n) = 2T(n/2) + \Theta(n)으로 쓴다.

4.1. The maximum-subarray problem

주식을 한 번 산 뒤 한 번 팔아서 가장 많은 이득을 내는 문제를 보자. 가장 싸게 사서 가장 비싸게 파는 방법을 생각할 수 있겠으나 이것은 정답이 아니다. 반례는 (10, 11, 7, 10, 6)이다.

A brute-force solution

무식한 방법으로 모든 경우의 수를 비교하는 Ω(n^2) 방법이 있다. 더 잘 할 수는 없을까?

A transformation

o(n^2) 방법을 위해서는 각각의 날의 가격이 아니라 각각의 날의 가격 변화를 본 뒤 합이 최대가 되는 부분배열을 찾으면 된다. 이를 최대 부분배열이라고 한다. 이것도 그냥 풀면 Θ(n^2)개의 부분배열을 보아야 하기 때문에 도움이 안 된다. 최대 부분배열 문제를 더 잘 푸는 방법을 생각해 보자.

참고로 최대 부분배열 문제는 음수인 원소가 있을 때에만 의미가 있다. 음수인 원소가 없다면 전체 배열이 답이 되기 때문이다.

A solution using divide-and-conquer

분할 정복으로 푼다면? A[low : high]를 왼쪽 부분배열 A[low : mid], 오른쪽 부분배열 A [mid + 1 : high]로 나눈다면 A[low : high]의 최대 부분배열은 두 배열에 속하거나 두 배열의 경계를 가로지를 것이다. 두 배열의 경계를 가로지르는 경우에 대해서는 A[i : mid], A [mid + 1 : j] 형태의 부분배열 중 가장 큰 것들을 찾은 뒤에 그것들을 합하면 된다. 이는 Θ(n)이다.

left-sum = -∞
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > left-sum
        left-sum = sum
        max-left = i
right-sum = -∞
sum = 0
for j = mid + 1 to high
    sum = sum + A[j]
    if sum > right-sum
        right-sum = sum
        max-right = j
return (max-left, max-right, left-sum + right-sum)

이를 이용한 최대 부분배열을 찾는 알고리즘은 다음과 같다.

FIND-MAXIMUM-SUBARRAY(A, low, high)
if high == low
    return (low, high, A[low]) // base case
else
    mid = floor((low + high) / 2)
    (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
    (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid + 1, high)
    (Cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, high)
    if left-sum ≥ right-sum and left-sum ≥ cross-sum
        return (left-low, left-high, left-sum)
    else if right-sum ≥ left-sum and right-sum ≥ cross-sum
        return (right-low, right-high, right-sum)
    else
        return (cross-low, cross-high, cross-sum)

Analyzing the divide-and-conquer algorithm

최대 부분배열 문제의 시간복잡도의 재귀식은 다음과 같게 된다.

T(n) = 2T(n/2) + \Theta(n) if n > 1, \Theta(1) if n = 1

=> T(n) = \Theta(n \lg n)

이 문제에 대한 선형 시간 알고리즘도 있다. 그 알고리즘은 분할 정복-재귀 기법을 쓰지 않는다.

4.2. Strassen’s algorithm for matrix multiplication

정사각 행렬을 곱하는 알고리즘은 다음과 같다. 이는 Θ(n^3)이다.

SQUARE-MATRIX-MULTIPLY (A, B)
n = A.rows
let C be a new n x n matrix
for i = 1 to n
    for j = 1 to n
        c_ij = 0
        for k = 1 to n
            c_ij = c_ij + a_ik * b_kj
return C

이보다 더 잘 할수 있는 알고리즘도 존재하는데, 스트라센의 알고리즘이 바로 그것이다. \Theta(n^{\lg 7}) = O(n^{2.81})의 시간 복잡도를 갖는다.

A simple divide-and-conquer algorithm

분할 정복을 이용해서 다음과 같이 풀 수 있다.

SQUARE-MATRIX-MULTIPLY-RECURSIVE(A, B)
n = A.rows
let C be a new n x n matrix
if n == 1
    c_11 = a_11 * b_11
else
    partition each of A, B and C into four n/2 x n/2 submatrices
    C_11 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_11, B_11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_12, B_21)
    C_12 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_11, B_12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_12, B_22)
    C_21 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_21, B_11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_22, B_21)
    C_22 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_21, B_12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A_22, B_22)
return C

행렬을 부분행렬로 분할할 때 메모리를 복사하지 말고 이미 있는 행렬의 인덱스를 참조하는 방법을 쓰면 시간복잡도를 줄일 수 있다.

이 때 시간복잡도는 다음과 같다. T(n) = 8T(n/2) + \Theta(n^2) if n > 1, \Theta(1) if n = 1

이는 Θ(n^3)이므로 사실 이득이 없다. 더 개선된 알고리즘으로 넘어가기 전에, 재귀식에서 점근항은 상수배를 무시할 수 있지만 부분 문제를 나타내는 항은 상수배를 무시할 수 없음을 눈여겨보자.

Strassen’s method

스트라센의 방법은 부분행렬의 곱을 8번이 아니라 7번만 함으로써 시간복잡도를 줄인다. 이에 대한 댓가로 부분행렬간의 덧셈을 하지만 상수번만 하므로 시간복잡도는 줄어든다. 스트라센의 방법은 다음의 4단계로 이루어진다:

  1. 입력 행렬 A, B와 출력 행렬 C를 n/2 x n/2 부분행렬로 나눈다. \Theta(1)이다.
  2. 10개의 부분행렬 S_1, …, S_10을 만든다. 각각은 A, B의 부분행렬의 합이거나 차이다. 이는 \Theta(n^{2}) 이다.
  3. 7개의 부분행렬을 만든다. 각각은 위에서 만든 10개의 부분행렬의 곱이다.
  4. C의 부분행렬 4개를 위에서 만든 7개의 부분행렬을 이용해 계산한다. 이는 \Theta(n^{2}) 이다.

따라서 시간복잡도를 구하는 재귀식은 T(n) = 7T(n/2) + \Theta(n^2) if n > 1, \Theta(1) if n = 1 이 되고, 총 시간복잡도는 \Theta(n^{\lg 7}) = \Theta(n^{2.81})이 된다.

2.번 과정에서 만드는 10개의 부분행렬은 다음과 같다.

S_{1} = B_{12} - B_{22}

S_{2} = A_{11} + A_{12}

S_{3} = A_{21} + A_{22}

S_{4} = B_{21} - B_{11}

S_{5} = A_{11} + A_{22}

S_{6} = B_{11} + B_{22}

S_{7} = A_{12} - A_{22}

S_{8} = B_{21} + B_{22}

S_{9} = A_{11} - A_{21}

S_{10} = B_{11} + B_{12}

3.번 과정에서 만드는 7개의 부분행렬은 다음과 같다.

P_{1} = A_{11} \cdot S_{1}

P_{2} = S_{2} \cdot B_{22}

P_{3} = S_{3} \cdot B_{11}

P_{4} = A_{22} \cdot S_{4}

P_{5} = S{5} \cdot S_{6}

P_{6} = S{7} \cdot S_{8}

P_{7} = S{9} \cdot S_{10}

이로부터 C의 부분행렬을 다음과 같이 계산할 수 있다.

C_{11} = P_{5} + P_{4} - P{2} + P{6}

C_{12} = P_{1} + P_{2}

C_{21} = P_{3} + P_{4}

C_{22} = P_{5} + P_{1} + P_{3} - P_{7}

4.3. The substitution method for solving recurrences

재귀식을 풀 때의 대입법은 두 단계로 이루어진다.

  • 답의 형태를 추측한다.
  • 수학적 귀납법으로 답에 붙는 계수들을 찾고, 해당 답을 검증한다.

예를 들어 T(n) = 2T(\lfloor n/2 \rfloor) + n의 재귀식의 답은 O(n lg n)인데, 이를 풀기 위해서는 수학적 귀납법을 사용해 이 추측한 답의 형태가 m < n에 대해 성립한다고 가정하고 이를 대입한다.

T(n) = 2 O(\lfloor n/2 \rfloor) \lg \lfloor n/2 \rfloor + n = O(n \lg n)

Making a good guess

이전에 본 것과 비슷한 재귀식이 있다면 비슷한 답을 추측에 적용해 본다. 다른 방법은 하한과 상한을 추측해본 뒤 이를 좁혀나가는 것이다.

Subtleties

재귀식의 답을 수학적 귀납법으로 증명할 때 약간의 트릭이 필요할 수도 있다. 다음 재귀식을 생각해보자.

T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1

이는 O(n)인데, 이를 증명하려면 재귀식의 가정을 T(n) ≤ cn이 아니라 T(n) ≤ cn – d로 놓아야 한다.

Avoiding pitfalls

T(n) = 2T(\lfloor(n/2)\rfloor) + n을 다음과 같이 O(n)이라고 틀리게 주장할 수 있다.

T(n) \leq 2(c(n/2)) + n \leq cn + n = O(n)

이것이 틀린 이유는 T(n) ≤ cn을 정확하게 증명하지 않았기 때문이다.

Changing variables

변수 변환으로 재귀식을 더 쉽게 풀 수도 있다.

T(n) = 2T(\lfloor(\sqrt{n})\rfloor) + \lg n 의 식은 m = \lg n을 대입하면 T(2^{m}) = 2T(2^{m/2}) + m으로 변한다. S(m) = T(2^{m})을 대입하면 S(m) = 2S(m/2) + m이 되며, S(m) = O(m \lg m)이 된다. 즉 T(n) = O(\lg n \lg \lg n)이다.

4.4. The recursion-tree method for solving recurrences

재귀 트리를 그림으로써 재귀식의 해법에 대한 직관을 더 쉽게 쌓을 수 있다. 여기서 각각의 노드는 재귀 실행에 드는 하나의 부분 문제의 수행 시간을 나타낸다. 각각의 노드의 수행 시간은 그 자식 노드들의 수행 시간의 총합과 같다.

4.5. The master method for solving recurrences

마스터 방법은 a \geq 1, b > 1이고 T(n)이 점근적으로 양수일 때 T(n) = aT(\frac{n}{b}) + f(n) 를 푸는 일반적인 방법을 제공한다.

Theorem 4.1 (Master theorem). a \geq 1, b > 1이고 f(n)은 함수, T(n)은 점근적으로 음이 아니고, 재귀식 T(n) = aT(\frac{n}{b}) + f(n) 가 주어져 있을 때,

  1. \epsilon > 0에 대해 f(n) = O(n^{\log_{b}a - \epsilon})이라면, T(n) = \Theta(n^{\log_{b} a})이다.
  2. f(n) = \Theta(n^{\log_{b}a})이라면, T(n) = \Theta(n^{\log_{b} a} \lg n) 이다.
  3. \epsilon > 0에 대해 f(n) = \Omega(n^{\log_{b}a + \epsilon})이고 c > 1과 적당히 큰 n에 대해 af(\frac{n}{b}) \leq cf(n)이라면, T(n) = \Theta(f(n)) 이다.

마스터 정리는 직관적으로 f(n)n^{\log_{b} a}를 비교한다. 1번 조건에서는 f(n)n^{\epsilon}만큼, 즉 다항식만큼 더 작아야 한다. 3번 조건은 f(n)이 다항식만큼 더 커야 한다는 조건에 추가로 정규식 조건인 af(\frac{n}{b}) \leq cf(n) 을 만족해야 한다. 그러므로 위의 3가지 경우는 전체 경우를 커버하지 못한다.

Using the master method

T(n) = 9T(n/3) + na = 9, b = 3, f(n) = n이므로 T(n) = \Theta(n^{\log_{3}9}) = \Theta(n^{2}) 이다.

T(n) = T(2n/3) + 1a = 1, b = 3/2, f(n) = 1이고 f(n) = \Theta(n^{\log{3/2}1}) = \Theta(1)이므로 T(n) = \Theta(n^{\log_{3/2}1} \lg n) = \Theta(\lg n) 이다.

T(n) = 3T(n/4) + n \lg na = 3, b = 4, f(n) = n \lg n이고 f(n) = \Omega(n^{\log{4}3 + 0.2})이고 3\frac{n}{4}\lg(\frac{n}{4}) \leq \frac{3}{4} n \lg n 이므로 T(n) = \Theta(f(n)) = \Theta(n \lg n) 이다.

T(n) = 2T(n/2) + n \lg nf(n)n보다 다항식만큼 더 크지 않으므로 마스터 방법으로 풀 수 없다.

T(n) = 2T(n/2) + \Theta(n)T(n) = \Theta(n \lg n)이다.

T(n) = 8T(n/2) + \Theta(n^{2})T(n) = \Theta(n^{3})이다.

T(n) = 7T(n/2) + \Theta(n^{2})T(n) = \Theta(n^{\lg 7})이다.

4.6. Proof of the master theorem

마스터 정리의 증명은 두 부분으로 이루어진다.

4.6.1. The proof of exact powers

우선 T(n)n = 1, b, b^{2}, \cdots에 대해서 푼다.

Lemma 4.2. a \geq 1, b > 1이고 f(n)b의 승수들에 대해 정의된 음이 아닌 함수라 하자. T(n) = \Theta(1) for n = 1, aT(\frac{n}{b}) + f(n) for n = b^{i}라 하면 T(n) = \Theta(n^{\log_{b} a}) + \sum_{j=0}^{\log_{b}n - 1} a^{j} f(\frac{n}{b^{j}}) 이 성립한다.

Lemma 4.3. a \geq 1, b > 1이고 f(n)b의 승수들에 대해 정의된 음이 아닌 함수라 하자. 함수 g(n) = \sum_{j=0}^{\log_{b}n - 1} a^{j} f(\frac{n}{b^{j}})b의 승수에 대해 다음과 같은 점근 상한을 가진다:

  1. \epsilon > 0에 대해 f(n) = O(n^{\log_{b}a - \epsilon})이라면, g(n) = \Theta(n^{\log_{b} a})이다.
  2. f(n) = \Theta(n^{\log_{b}a})이라면, g(n) = \Theta(n^{\log_{b} a} \lg n) 이다.
  3. \epsilon > 0에 대해 f(n) = \Omega(n^{\log_{b}a + \epsilon})이고 c > 1과 적당히 큰 n에 대해 af(\frac{n}{b}) \leq cf(n)이라면, g(n) = \Theta(f(n)) 이다.

Lemma 4.4. a \geq 1, b > 1이고 f(n)b의 승수들에 대해 정의된 음이 아닌 함수라 하자. T(n) = \Theta(1) for n = 1, aT(\frac{n}{b}) + f(n) for n = b^{i}라 하면 T(n)b의 승수에 대해 다음과 같은 점근 상한을 가진다:

  1. \epsilon > 0에 대해 f(n) = O(n^{\log_{b}a - \epsilon})이라면, T(n) = \Theta(n^{\log_{b} a})이다.
  2. f(n) = \Theta(n^{\log_{b}a})이라면, T(n) = \Theta(n^{\log_{b} a} \lg n) 이다.
  3. \epsilon > 0에 대해 f(n) = \Omega(n^{\log_{b}a + \epsilon})이고 c > 1과 적당히 큰 n에 대해 af(\frac{n}{b}) \leq cf(n)이라면, T(n) = \Theta(f(n)) 이다.

4.6.2. Floors and ceilings

이를 floor와 ceiling 연산을 이용해 일반적인 자연수 n에 대해 확장하면 된다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중