1부터 n까지 합을 구하는 방법을 for문으로 하는 방식과 단순 재귀함수를 이용하는 방식을 이전 블로그(http://hijuworld.tistory.com/3)에서 다뤘는데 이번에는 분할 정복 방식을 이용해서 구하는 함수에 대해서 알아 보겠습니다.
1 2 3 4 5 6 7 8 | 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); } | cs |
1부터 n까지 합을 반으로 쪼개면 다음과 같습니다.
뒷부분에 공통적으로 
앞부분 
그래서 아래와 같은 점화식을 구할 수 있습니다.
해당 점화식을 코드로 옮긴 것은 위의 코드 입니다.
해당 함수의 빅오는 
for문을 이용해서 합을 구하는 방식은 O(n) 입니다.
아래 코드를 가지고 테스트를 해보면 해당 분할 정복 방식이 코드는 복잡해 보이지만 속도 면에서는 월등히 압서는 것을 볼 수 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #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; } | cs |
-실행 결과 -
분할정복 시간 측정 : 0.000000
for 시간 측정 : 2746.000000
계속하려면 아무 키나 누르십시오 . . .
측정 결과를 보면 분할정복 방식은 1ms 미만이라 0으로 나오며 for문을 이용한 방식은 2746ms로 시간차이가 많이 나는 것을 알 수 있습니다.
많은 양의 숫자를 더할때는 분할 정복을 이용하는 것을 추천 합니다.
참고 서적 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (저자 구종만 지음, 인사이트 출판)
'알고리즘' 카테고리의 다른 글
| C++ 스택(Stack), 연결 리스트(LinkedList) 코드 (0) | 2018.06.07 |
|---|---|
| 구간 합, 구간 최대값 등 구하기 (세크먼트 트리 Segment Tree 이용) (0) | 2018.06.02 |
| C/C++ 2진 탐색(Binary Search) 예제 코드 (0) | 2018.05.24 |
| C/C++ 병합정렬(Merge Sort) 코드 (0) | 2018.05.24 |
| 1부터 n까지 합계 함수(for와 재귀) (0) | 2018.03.30 |
