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

알고리즘 2018. 4. 2. 21:15

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까지 합을 반으로 쪼개면 다음과 같습니다.

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


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





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


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





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


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

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
Posted by 꿈만은공돌
,

C++ STL 두 Vector 중복 인자 제거 함수

C, C++ 2018. 3. 31. 12:29



Vector a 에서 vector b와 겹치는 인자를 제거한 결과를 반환하는 함수 이다.


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
52
 
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::vector;
 
vector<int> duplication(vector<int>& a, vector <int>& b) {
    vector<int>::iterator iter;
    vector<int>::iterator iter_b;
    vector<int> c = a; //a의 값 복사
    
    for (iter_b = b.begin(); iter_b != b.end(); iter_b++) {
        for (iter = c.begin(); iter != c.end();) {
            if (*iter == *iter_b)
                iter = c.erase(iter); //중복 제거
            else
                iter++;            
        }        
    }
    return c; //결과 반환
}
 
int main() {
    vector<int> a;
    vector<int> b;
 
    a.push_back(1);
    a.push_back(3);
    a.push_back(-1);
    a.push_back(11);
    a.push_back(-5);
    
    b.push_back(-1);
    b.push_back(-5);
    b.push_back(4);
 
    vector<int> c = duplication(a,b); //a에서 b와 겹치는 인자 제거한 결과 반환
    
    //원본 a출력
    for (vector<int>::iterator iter = a.begin(); iter != a.end(); ++iter) 
        cout << *iter <<" ";
    cout << endl;
 
    //b와의 중복 제거된 c출력
    for (vector<int>::iterator iter = c.begin(); iter != c.end(); ++iter) 
        cout << *iter << " ";    
    cout << endl;
 
    return 0;
}
 
cs


- 출력 결과 -



1 3 -1 11 -5

1 3 11

'C, C++' 카테고리의 다른 글

C, C++ 에서 동적 메모리의 할당(malloc, new)과 해제(free,delete) 원리  (0) 2018.04.30
포인터 배열 VS 배열 포인터 차이 및 예제  (0) 2018.04.30
[c/c++] memset()을 이용한 배열에 값을 모두 0또는 -1로 초기화  (0) 2018.04.08
C++ STL Vector 기본 생성, 추가, 삭제  (0) 2018.03.30
C, C++ 프로그램 실행 시간 측정  (1) 2018.03.29
Posted by 꿈만은공돌
,

C++ STL Vector 기본 생성, 추가, 삭제

C, C++ 2018. 3. 30. 19:27



C++ 에서 표준 템플릿 라이브러리인 STL(Standard Template Library)의 가장 기본적인 시퀀스 컨테이너인 vector에 대해서 설명하겠습니다.

기본적으로 배열과 비슷한 부분이 많이 있습니다.

#include<vector> 헤더파일을 포함시켜 주시고 사용하면 됩니다.

선언을 할때 vector<int> v와 같은 방식으로 선언을 하며 크기를 vector<int> v(10) 과 같이 임의 지정할 수도 있습니다.

vector에 저장할 수 있는 크기가 있으며 그것을 초과 할 경우 vector에 인자들을 복사하여 다른 메모리에 할당하면서 크기를 늘립니다.



1. 기본 선언과 인자 추가 , 탐색

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
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
using std::vector;
 
int main() {
    //선언
    vector<int> v;

    //가장뒤에 인자추가
    v.push_back(5);        // [5]
    v.push_back(15);    // [5, 15]
    v.push_back(25);    // [5, 15, 25]
    v.push_back(1);        // [5, 15, 25, 1]
    
    //탐색
    for (unsigned int i = 0; i < v.size(); i++) {
        cout << v[i] << endl;
    }
    
    cout << "----------"<<endl;
                     
    //탐색2 iterator 이용하기
    vector<int>::iterator iter;
    for (iter = v.begin(); iter != v.end(); iter++) {
        cout << *iter << endl;
    }
    return 0;
}






2. size() 와 clear()

1
2
3
4
5
6
7
8
9
10
11
12
int main() {
    vector<int> v;
    v.push_back(-11);        
    v.push_back(-22);
    v.push_back(33);
    
    //사이즈 측정 및 초기화 함수
    cout << v.size() << endl;    // 3 출력
    v.clear();                    // vector 내용 초기화
    cout << v.size() << endl;    // 0 출력
    return 0;
}




3. 중간에 인자 넣기( insert())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
    vector<char> v;
    v.push_back('a');
    v.push_back('b');
    v.push_back('d');
    v.push_back('e');
 
    //b 다음에 c 삽입하기
    vector<char>::iterator iter;
    for (iter = v.begin(); iter != v.end(); ++iter) {
        if (*iter == 'b') {    //b찾기
            v.insert(iter+1, 'c');    //b다음에 c 삽입하기
            break;
        }
    }
 
    //결과 출력
    for (iter = v.begin(); iter != v.end(); ++iter) {
        cout << *iter << endl;
    }
    return 0;
}




4. 인자 삭제하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main() {
    vector<double> v;
    v.push_back(1.1);
    v.push_back(3.3);
    v.push_back(-1.3);
    v.push_back(11);
    v.push_back(-5);
 
    //음수 제거하기
    vector<double>::iterator iter;
    for (iter = v.begin(); iter != v.end(); ) {
        if (*iter < 0) {            // 음수 찾기
            iter = v.erase(iter);    // 인자 삭제, 삭제 후 다음 인자 반환
        } else {
            ++iter;
        }
    }
 
    //결과 출력
    for (iter = v.begin(); iter != v.end(); ++iter) {
        cout << *iter << endl;
    }
    return 0;
}




'C, C++' 카테고리의 다른 글

C, C++ 에서 동적 메모리의 할당(malloc, new)과 해제(free,delete) 원리  (0) 2018.04.30
포인터 배열 VS 배열 포인터 차이 및 예제  (0) 2018.04.30
[c/c++] memset()을 이용한 배열에 값을 모두 0또는 -1로 초기화  (0) 2018.04.08
C++ STL 두 Vector 중복 인자 제거 함수  (0) 2018.03.31
C, C++ 프로그램 실행 시간 측정  (1) 2018.03.29
Posted by 꿈만은공돌
,

티스토리툴바