분할 정복을 이용한 수열의 빠른 합

아래 내용은 종만북을 공부한 후 나중에 복습용으로 정리한 것입니다.

 

1. 수열의 빠른 합.

보통 수열의 합은 단순히 

$$ \sum_{k = 1}^N k = \frac{\left(n\right)\left(n+1\right)}{2} $$

이런식으로 공식을 이용하면 \( O \left( 1 \right) \)의 시간복잡도로 바로 계산이 가능합니다. 

하지만 분할 정복을 공부하기 위해 이번에는 \(  \sum_{k=1}^n k \) 을 분할 정복을 이용해 구현해 보겠습니다.

 

재귀 호출

우선 먼저 일반적인 재귀 호출을 이용한 코드입니다.

 

int recursiveSum(int n) {
    // 기저 조건.
    if(n == 1) return 1;
    return n + recursiveSum(n - 1);
}

 

가장 쉽게 떠올릴 수 있고, 구현이 가능한 코드입니다. 시간복잡도는 \( O \left( N \right) \)이 됩니다.

 

분할 정복

다음은 분할 정복을 이용해서 같은 일을 하는 \( fastSum \left( n \right) \)함수를 작성하겠습니다. 그 전에 분할정복을 어떻게 적용할지 아이디어를 먼저 떠올려 봅시다.

 

$$  fastSum\left(\right)=1+2+\cdots+n=\left(1+2+\cdots+\frac{n}{2}\right)+\left(\left(\frac{n}{2}+1\right)+\cdots+n\right) $$

 

반으로 잘라서 2개의 부분문제를 생성했습니다. 첫번째 조각을 잘 살펴보면 1 부터 \( \frac{n}{2} \) 까지의 합을 계산합니다. \(fastSum\left(n\right) \) 함수는 1부터 n 까지의 합을 계산하는 함수임을 기억해본다면, 첫번째 조각은 \( fastSum\left(\frac{n}{2}\right) \) 임을 알 수 있게 됩니다.

 

하지만 두번째 조각은 \( fastSum \left( \right) \) 함수로 표현할 수 없습니다. 1부터 n까지의 합 형태만 함수로 나타낼 수 있기 때문입니다. 그러면 어떻게 해야할까요? \( fastSum \left( \right) \)함수로 나타낼 수 있도록 한번 변형해 보겠습니다.

$$ \left( \left( \frac{n}{2} + 1 \right) + \cdots +n \right) = \left( \frac{n}{2} + 1 \right) + \left( \frac{n}{2} + 2 \right) + \cdots + \left( \frac{n}{2} + \frac{n}{2} \right) $$

 

변형한 식을 자세히 살펴보면 \( \frac{n}{2} \) 가 계속 반복해서 등장하는 것을 발견할 수 있습니다. 걔네들만 따로 빼서 식을 정리하면,

 

$$ \left( \frac{n}{2} \times \frac{n}{2} \right) + \left( 1 + 2 + \cdots + \frac{n}{2} \right) $$

 

이렇게 정리됩니다. 이 때 1부터 \( \frac{n}{2} \) 까지 더하는 항을 찾을 수 있는데, 이는 \( fastSum \left( \frac{n}{2} \right) \) 로 변형이 가능합니다.

즉, \( fastSum \left( n \right) \) 함수를 재귀적으로 표현하게 되면,

 

$$ fastSum \left( n \right) = 2 \times fastSum \left( \frac{n}{2} \right) + \frac{n^2}{4}  $$

 

이렇게 표현할 수 있겠네요. 참고로 n 이 짝수 라고 가정했을 때만 성립합니다.

 

이제 코드로도 한번 구현해 보겠습니다.

 

int fastSum(int n) {
    // 기저 조건.
    if(n == 1) return 1;
    // n 이 홀수인 경우.
    if(n % 2 == 1) return fastSum(n - 1) + n;
    return 2 * fastSum(n/2) + (n/2)*(n/2);
}

 

 

n이 홀수 인 경우도 문제 없죠. 단순히 n-1까지의 합에 n 만 더해주면 되니까요.

분할정복이 일반적으로 계산하는 것보다 훨씬 빠르다고 알려져 있습니다. 그렇기 때문에 이 고생을 해가며 점화식을 구해서 분할정복을 적용해서 코드를 구현했습니다. 진짜로 더 빠른지 시간복잡도를 간단하게 구해봅시다.

 

만약  \( fastSum \left( 32 \right) \) 를 구한다고 가정해봅시다. 그러면 \( 2 \times fastSum \left( 16 \right) + \frac{32^2}{4}\) 이 유도됩니다. 음... 뒤에 있는 분수항은 상수이므로 그냥 무시하고 함수의 호출만 살펴보겠습니다.

 

$$ fastSum \left( 32 \right) \Rightarrow fastSum \left( 16 \right) \Rightarrow fastSum \left( 8 \right) \Rightarrow fastSum \left( 4 \right) \Rightarrow fastSum \left( 2 \right) \Rightarrow fastSum \left( 1 \right)$$

 

이런식으로 함수가 호출되겠죠. 이런식으로 단순히 절반씩 줄어드는 경우에는 시간복잡도는 \( O \left( logN \right) \) 이 됩니다.

\( O \left( logN \right) \) 은 거의 상수라고 생각해도 무방할 정도로 작은 수이죠. 단순 재귀로 구현했을 때 보다 훨씬 빠릅니다.