분할 정복을 이용 1부터 n까지 합 구하는 함수, 알고리즘

1부터 n까지 합을 구하는 방법을 for문으로 하는 방식과 단순 재귀함수를 이용하는 방식을 이전 블로그(http://hijuworld.tistory.com/3)에서 다뤘는데 이번에는 분할 정복 방식을 이용해서 구하는 함수에 대해서 알아 보겠습니다.

int divSum(int n) {
    if (n == 1)
        return 1;
    if (n % 2 == 1)
        return divSum(n - 1) + n;
    else
        return divSum(n / 2)*2 + (n / 2)*(n / 2);
}

1부터 n까지 합을 반으로 쪼개면 다음과 같습니다.

뒷부분에 공통적으로  이 개 존재합니다. 이를 하나로 묶으면

 이 공통적으로 존재하기 때문에 하나로 묶으면 아래와 같이 정리가 됩니다.

앞부분  은 처음 구하려고 한 1 부터 N까지에  절반인 1부터  까지의 합니다.

그래서 아래와 같은 점화식을 구할 수 있습니다.

해당 점화식을 코드로 옮긴 것은 위의 코드 입니다.

해당 함수의 빅오는  와 같습니다.

for문을 이용해서 합을 구하는 방식은 O(n) 입니다.

아래 코드를 가지고 테스트를 해보면 해당 분할 정복 방식이 코드는 복잡해 보이지만 속도 면에서는 월등히 압서는 것을 볼 수 있습니다.

#include <iostream>
#include <time.h>
using std::cout;
using std::endl;
 
int divSum(int n)  //분할 정복 방식
{
    if (n == 1)
        return 1;
    if (n % 2 == 1)
        return divSum(n - 1) + n;
    else
        return divSum(n / 2)*2 + (n / 2)*(n / 2);
}
int forSum(int n) // for 이용 방식
{
    int sum=0;
    for (int i = 1; i <= n; i++)
        sum += i;
    return sum;
}
int main() {
    clock_t start, end;
    double result;
    //분할 정복 방식
    start = clock(); 
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    divSum(200000000);
    end = clock(); 
    result = (double)(end - start);
    printf("분할정복 시간 측정 : %f\n", result);
 
    //for문 이용방식
    start = clock();
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    forSum(200000000);
    end = clock();
    result = (double)(end - start);
    printf("for 시간 측정 : %f\n", result);
    return 0;
}

-실행 결과 - 

분할정복 시간 측정 : 0.000000

for 시간 측정 : 2746.000000

계속하려면 아무 키나 누르십시오 . . .

측정 결과를 보면 분할정복 방식은 1ms 미만이라 0으로 나오며 for문을 이용한 방식은 2746ms로 시간차이가 많이 나는 것을 알 수 있습니다.

많은 양의 숫자를 더할때는 분할 정복을 이용하는 것을 추천 합니다.

참고 서적 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (저자 구종만 지음, 인사이트 출판)