[ 혼연 정리 ] STL 알고리즘 - 9 [ 수치 알고리즘 ]

ㅇ 수치 알고리즘
 - STL에 직접 소속되지 않으며 C++ 라이브러리로 분류된다.
 - 수치 알고리즘도 STL 컨테이너와 함께 동작한다.
 - numeric 헤더 파일에 정의되어 있다.

ㅇ 누적합을 구하는 함수

T accumulate(InIt first, InIt last, T val [, BinOp op]);
OutIt partial_sum (InIt first, InIt last, OutIt result [ ,BinOp op]);

 - accumulate 함수 : first ~ last 구간에 속한 값들의 총합 , 세번째 인수 val은 누적 총합의 초기값인데 0으로 지정하면  순수한 합을 구할 수 있다.
 - partial_sum 함수 : first ~ last까지의 부분합들을 구해 result 반복자 위치에 순서대로 대입

1 #include <iostream>
2 #include <vector>
3 #include <numeric>
4 #include <algorithm>
5
6 using namespace std;
7
8 template<typename C>
9 void dump(const char *desc, C c)

10 {
11     cout.width(12);cout << left << desc << "==> ";
12     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
13     cout << endl;
14 }
15
16
17 void main()
18 {
19     int ar1[]={49,26,19,77,34,52,84,34,92,69};
20     vector<int> vi1(&ar1[0],&ar1[10]);
21     printf("벡터의총합은%d이다.\n",accumulate(vi1.begin(),vi1.end(),0));
22
23     int ar2[]={1,2,3,4,5,6,7,8,9,10};
24     vector<int> vi2(&ar2[0],&ar2[10]);
25     vector<int> vi3;
26     partial_sum(vi2.begin(),vi2.end(),back_inserter(vi3));
27     dump("부분합", vi3);

- accumulate 함수는 반복자 구간을 순회하면서 이 값들을 계속 더하여 전체 총합을 만들어 낸다.
- 이때 별로의 함수 객체를 지정하면 더하기가 아닌 다른 연산을 할수있다.
- 예) accumulate(vi1.begin(), vi1.end(), 1, multiplies<int>()) 연산을 하면 모든 요소의 누적곱이 구해진다

ㅇ adjacent_difference()
 
OutIt adjacent_difference(InIt first, InIt last, OutIt result [ ,BinOp op]);

 - 인접 요소들의 차를 계산해 result 반복자에 차례대로 대입

1 #include <iostream>
2 #include <vector>
3 #include <numeric>
4 #include <algorithm>
5
6 using namespace std;
7
8 template<typename C>
9 void dump(const char *desc, C c)

10 {
11     cout.width(12);cout << left << desc << "==> ";
12     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
13     cout << endl;
14 }
15
16
17 void main()
18 {
19
20      int ar[]={1,2,5,10,15,12,20};
21      vector<int> vi(&ar[0],&ar[7]);
22      vector<int> vi2;
23      adjacent_difference(vi.begin(),vi.end(),back_inserter(vi2));
24      dump ("부분차",vi2);
25 }

ㅇ 순열 생성기

 - 요소들을 순서대로 배치하는 바업ㅂ

 bool next_permutation(BiIt first, BiIt last [, BinPred F]);
 bool prev_permutation(BiIt first, BiIt last [, BinPred F]);

 - 두 함수는 반복자 구간에 있는 요소의 현재값에 대한 다음, 이전 순열을 계산한다.
- 이전 순열이라는 것은 값의 대소 관계를 기준으로 하며 별도의 함수 객체로 이 관계를 지정할 수 있다.

1 #include <iostream>
2 #include <vector>
3 #include <numeric>
4 #include <algorithm>
5
6 using namespace std;
7
8 template<typename C>
9 void dump(const char *desc, C c)

10 {
11     cout.width(12);cout << left << desc << "==> ";
12     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
13     cout << endl;
14 }
15
16
17 void main()
18 {
19      int i;
20      vector<int> vi;
21      vi.push_back(1);vi.push_back(2);vi.push_back(3);
22      dump("원본",vi);
23      for (i=0;i<6;i++) {
24           next_permutation(vi.begin(),vi.end());
25           dump ("다음",vi);
26      }
27 }

ㅇ inner_product()

 - 내적( 두 구간의 대응되는 요소끼리 곱한 후 전체를 더한 값)을 한다

T inner_product(InIt1 first1, InIt1 last1, InIt2 first2, T val [, BinOp op1, BinOp op2]);

 - 두개의 반복자 구간과 초기값 val을 지정하며 내적 계산에 사용될 두 개의 이항 함수 객체를 지정할 수 있다.

 1 #include <iostream>
2 #include <vector>
3 #include <numeric>
4 #include <algorithm>
5
6 using namespace std;
7
8 void main()
9 {
10      int inp;
11      vector<int> vi1,vi2;
12      vi1.push_back(2);vi1.push_back(3);vi1.push_back(4);
13      vi2.push_back(5);vi2.push_back(6);vi2.push_back(7);
14      inp=inner_product(vi1.begin(),vi1.end(),vi2.begin(),0);
15      printf("내적 = %d\n",inp);
16 }

 ㅇ  lexicographical_compare ()
bool lexicographical_compare (InIt1 first1, InIt1 last1, InIt2 first2 [, BinPred F]);

- 두 구간의 대응되는 요소를 차례대로 비교하는데 첫 번째 요소가 두번째 요소보다 작으면  true를 리하고 크면 false를 리턴하며 즉시 종료
- 같다면 다음 요소를 똑같은 방식으로 계속 비교하기를 구간끝까지 반복
 - 디폴트 비교 함수 객체가 less 이므로 첫번째 구간이 두번째 구간보다 작아야만 true를 리턴, 작지 않으면 false가 리턴
- 만약 첫번째 구간이 먼저 끝나고 두번째 구간은 아직 값이 남아 있으면 이 경우는 true를 리턴

1 #include <iostream>
2 #include <vector>
3 #include <numeric>
4 #include <algorithm>
5
6 using namespace std;
7
8 void main()
9 {
10
11 vector<int> vi1,vi2;
12     for (int i=8;i<16;i++)
13     {
14         vi1.push_back(i);
15         vi2.push_back(i);
16     }
17     //vi1[5]=0;
18     if (lexicographical_compare(vi1.begin(),vi1.end(),vi2.begin(),vi2.end()))
19     {
20         cout << "vi1이더작다" << endl;
21     }
22     else
23     {
24         cout << "vi1이더작지않다" << endl;
25     }
26 }

 ㅇ 힙연산

 - 힙(heap)은 흔히 기억 장소의 자유 영역을 의미하는데 자료구조에서 말하는 힙은 다음과같은 조건을 만족하는 자료 구조를 의미한다.

① 첫 번째 요소가 구간에서 가장 크다.  ==> 크기가 제일 큰것을 요구함, 정렬되지 않아도 상관없다.
② 푸시, 팝 연산이 로그 시간내로 수행될 수 있다.

  - 힙연산 함수들은 우선 순위 큐 구현에 흔히 사용되는데 STL의 proriy_queue 어뎁터가 이런 자료구조를 잘 제공하므로 힙연산 함수들을 직접 사용할 일은 거의 없다.
 
void make_heap(RanIt first, RanIt last [,BinPred F]);
void sort_heap(RanIt first, RanIt last [,BinPred F]);
void push_heap(RanIt first, RanIt last [,BinPred F]);
void pop_heap(RanIt first, RanIt last [,BinPred F]);

 - 모두 원형은 동일, 적용할 구간을 인수로 전달받고 원할 경우 조건자를 지정할 수도 있다.
 - 디폴트 조건자는 less이다.
 - make_heap 함수 : first ~ last-1을 구간으로 만드는데 가장 큰값을 선두로 보낸다. 즉 first가 가장 커야 한다.
 - push_heap 함수 : 원래의 힙보다 하나 더 확장된 범위인 first ~ last를 힙으로 만드는데 곧 last를 포함해서 제일 큰값을 앞으로 보내는 것, 통상 push_heap 이전에 push_back이 먼저 호출
 - pop_heap 함수 : fisrt에 있는 제일 큰 요소를 제일 뒤로 보내고 나머지 first ~ last -1 구간을 다시 힙으로 만든다. (first를 제일 앞으로)
 - sort_heap 함수 : 힙 구간을 오름차순으로 정렬하는데 일반적인 정렬 함수보다는 훨씬 더 빠르다.

1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5 using namespace std;
6
7 template<typename C>
8 void dump(const char *desc, C c)
9 {
10     cout.width(12);cout << left << desc << "==> ";
11     copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," "));
12     cout << endl;
13
14 }
15
16 void main()
17 {
18      int ar[]={5,3,2,9,6};
19      vector<int> vi(&ar[0],&ar[5]);
20      dump("원본",vi);
21      make_heap(vi.begin(),vi.end());
22      dump("make_heap",vi);
23      vi.push_back(10);
24      push_heap(vi.begin(),vi.end());
25      dump("push_heap",vi);
26      pop_heap(vi.begin(),vi.end());
27      dump("pop_heap",vi);
28      vi.pop_back();
29      sort_heap(vi.begin(),vi.end());
30      dump("sort_heap",vi);
31 }

ps : 출처 및 자세한 내용은  www.WinAPI.co.kr 참고