STL algorithm
 대문  주제별 보기  함수사전  코드모음  바뀐글  목록   Anonymous
총 페이지 수 : 3224

전체 함수/용어사전
Facebook Joinc 그룹   Joinc QA 사이트
현재위치 : article>STL_algorithm



joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.

<a href="/modules/moniwiki/wiki.php/manSearch?google=none&name=STL">STL</a>(5) - algorithm

STL(5) - algorithm

윤 상배

dreamyun@yahoo.co.kr

차례
1절. algorithm 에 대해서
2절. 알고리즘
2.1절. None-mutating algorithms
2.1.1절. find
2.1.2절. count
2.2절. Mutating algorithms
2.2.1절. copy
2.2.2절. swap
2.2.3절. reverse
2.2.4절. remove
2.2.5절. random_shuffle
2.2.6절. unique
2.3절. Sorting 알고리즘들
2.3.1절. sort
2.3.2절. lower_bound 와 upper_bound
2.3.3절. merge
2.3.4절. set_union, set_intersection, set_difference
2.4절. Generalized numeric algorithms
2.4.1절. accumulate
2.4.2절. partical_sum
2.4.3절. adjacent_difference
2.4.4절. inner_product

1절. algorithm 에 대해서

지금까지 STL 의 여러가지 기능에 대해서 알아보았는데, 이러한 기능들은 결국 STL 을 이용한 자료구조로써의 기능에 촛점이 맞추어져 있음을 알수 있다. STL은 이러한 자료구조를 쉽고 유연하게 구현해주기 위한 도구라고 할수 있을것이다.

자료구조가 사용되면 빠지지 않고 따라다니는게 있는데, 바로 알고리즘 들이다. (아마도 가장 많이 사용되는게 sort, search 과 같은 알고리즘들일것이다.)

STL 에서는 여러가지 컨테이너들로 구성된 자료구조의 연산을 위한 다양한 알고리즘을 제공한다.

2절. 알고리즘

알고리즘을 사용하기 위해서는 다음과 같이 헤더파일을 선언해 주어야 한다. 

	
#include <algorithm>

STL에서 제공하는 알고리즘들은 그 특성에 따라서 몇가지 종류로 분류할수 있다. "Non-mutating algorithms", "Mutating algorithms", "Sorting algorithms", Generalized numeric algorithms" 등이다.

이제 부터 이러한 분류별로 각각의 분류에 포함된 알고리즘을 설명하도록하겠다. 그러나 워낙에 많은 알고리즘이 존재하고 (대략 50여가지) 이들 알고리즘중에는 거의 사용되어지지 않는 알고리즘들도 있으므로, 자주 사용된다고 생각되는 알고리즘들만을 설명하도록 할것이다. 나머지 알고리즘에 대한 정보를 알기를 원한다면 SGI STL 홈 문서를 참고하길 바란다.

2.1절. None-mutating algorithms

mutating 은 "변화", "변경" 의 뜻을 가진다. None-mutating algorithms 에 포함되는 알고리즘들은 컨테이너들의 원소에 대해서 None-mutating 즉 컨테이너를 변경시키지 않는 특성을 가지고 있다.

예를들어서 search 나, 원소의 갯수를 세는 count 등의 알고리즘은 컨테이너에서 필요한 원소를 찾거나, 계수를 하는 일을 할뿐으로, 컨테이너를 변경(원소를 삭제하거나, 위치를 변경시키거나)하는 일을 수행하지 않을것이다. 그런이유로 이러한 알고리즘들을 None-mutating(변경불가) 알고리즘이라고 부른다. (말은 무지 복잡한데 개념은 무지 간단하다는걸 알수 있을것이다.)

2.1.1절. find

아마도 가장많이 사용되는 알고리즘일 것이다. 컨테이너에서 일정한 범위의 원소들사이에서 원하는 값을 찾는다. 이 범위는 iterator 로 주어진다. 


template<class InputIterator, class EqualityComparable>
InputIterator find(InputIterator first, InputIterator last,
                   const EqualityComparable& value);
돌려주는 값은 역시 iterator 이며, 이 iterator 은 찾은 원소가 컨테이너에서 위치하는 값을 가리킨다. 
#include <algorithm>
#include <vector>

int main()
{
    vector<int> V;

    V.push_back(1);
    V.push_back(4);
    V.push_back(7);
    V.push_back(5);

    vector<int>::iterator mi;

    mi = find(V.begin(), V.end(), 4);

    cout << *mi << endl;
}

2.1.2절. count

count 는 말그대로 컨테이너에 포함된 원소의 갯수를 계수하기 위해서 사용된다. 

iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, 
      const EqualityComparable& value);
첫번째와 두번째 아규먼트로 주어지는 iterator 를 순환하면서 세번째 아규먼트로 주어지는 value 와 일치하는 값이 있는지 확인하여서 이 값을 계수한다. 
#include <algorithm>
#include <vector>

int main()
{
    vector<int> V;

    V.push_back(1);
    V.push_back(4);
    V.push_back(1);
    V.push_back(7);
    V.push_back(1);

    cout << count(V.begin(), V.end(), 1) << endl;
}

2.2절. Mutating algorithms

이것들은 변경가능한 알고리즘들로써, 컨테이너의 원소를 수정할수 있다. 컨테이너 원소를 복사하거나, 교체, 삭제 하는등의 작업을 수행한다. 이러한 작업 수행중에 원소의 내용이 변경되므로 Mutating 알고리즘이라고 한다.

2.2.1절. copy

copy 는 Iterator 로 주어지는 범위의 원소를 다른 컨테이너로 복사하고자 할때 사용한다. 

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
                    OutputIterator result);
첫번째 아규먼트와 두번째 아규먼트로 주어지는 Iterator 사이를 순환하며, 이들 Iterator 사이의 원소들을 result 이테레이터로 복사한다. 
#include <algorithm>
#include <vector>
#include <list>

int main()
{
    vector<int> V;
    list<int> L(5);

    V.push_back(1);
    V.push_back(2);
    V.push_back(3);
    V.push_back(4);
    V.push_back(5);

    copy(V.begin(), V.end(), L.begin());

    list<int>::iterator mi = L.begin();

    while(mi != L.end())
    {
        cout << *mi << endl;
        *mi++;
    }
}
list 를 선언할때 크기를 5로 지정한걸 주목하라. copy 알고리즘은 자동적으로 컨테이너의 크기를 할당시켜주지 않으므로, 미리 복사될 컨테이너의 크기를 지정해 놓아야 한다. list 를 크기를 할당시키지 않고 copy 해보면 컨테이너의 크기가 할당되지 않으므로, 하나의 값만이 복사됨을 알수 있을것이다. 이럴경우 list 컨테이너에는 5 하나만 들어가게 될것이다.

2.2.2절. swap

swap 는 인자로 주어진 2개의 컨테이너의 원소를 교환하기 위해서 사용된다. 

template <class Assignable> 
void swap(Assignable& a, Assignable& b);
다음은 swap 를 사용한 간단한 예이다. 
#include <algorithm>
#include <vector>

int main()
{
    vector<int> V1;
    vector<int> V2;

    V1.push_back(3);
    V1.push_back(2);

    V2.push_back(100);
    V2.push_back(200);

    swap(V1, V2);

    cout << V1[0] << endl;
    cout << V2[0] << endl;
    cout << V2[1] << endl;
}

2.2.3절. reverse

컨테이너의 원소를 뒤바꾼다. 즉 첫번째 원소는 마지막으로, 마지막원소는 첫번째로 교환하게 된다. 이러한 과정이 아규먼트로 주어진 iterator 사이의 모든 원소에 대해서 발생하게 된다. 

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
				

#include <algorithm>
#include <vector>

int main()
{
    vector<char> V;

    V.push_back('a');
    V.push_back('b');
    V.push_back('c');
    V.push_back('d');

    copy(V.begin(), V.end(), ostream_iterator<char>(cout, " "));
    // a b c d 가 출력된다. 
    cout << endl;

    reverse(V.begin(), V.end());
    copy(V.begin(), V.end(), ostream_iterator<char>(cout, " "));
    // d c b a 가 출력된다. 
    cout << endl;

}

2.2.4절. remove

iterator 범위내에서 일치되는 특정 원소를 삭제하고자 할때 사용한다. 

template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
                       const T& value);
				

#include <algorithm>
#include <list>

int main()
{
    list<int> L;

    L.push_back(1);
    L.push_back(2);
    L.push_back(5);
    L.push_back(1);
    L.push_back(3);

    copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    // 1 2 5 1 3 이 출력될것이다. 

    list<int>::iterator mi = remove(L.begin(), L.end(), 1);
    copy(L.begin(), mi, ostream_iterator<int>(cout, " "));
    cout << endl;
    // 2 5 3 이 출력될것이다. 
}

2.2.5절. random_shuffle

꽤 재미있는 알고리즘이다. 컨테이너에 포함된 원소를 랜덤하게 위치를 재배열 해주는 일을한다. 

template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
				

#include <algorithm>
#include <vector>

int main()
{
    vector<char> V;

    V.push_back('a');
    V.push_back('b');
    V.push_back('c');
    V.push_back('d');
    V.push_back('e');

    copy(V.begin(), V.end(), ostream_iterator<char>(cout, " "));
    cout << endl;

    random_shuffle(V.begin(), V.end());
    copy(V.begin(), V.end(), ostream_iterator<char>(cout, " "));
    cout << endl;

    random_shuffle(V.begin(), V.end());
    copy(V.begin(), V.end(), ostream_iterator<char>(cout, " "));
    cout << endl;

    random_shuffle(V.begin(), V.end(), 2);
    copy(V.begin(), V.end(), ostream_iterator<char>(cout, " "));
    cout << endl;
}

2.2.6절. unique

이것은 컨테이너중에 중복된 요소를 없앰으로 오직 유일한 요소들만을 가지도록 만들어준다. 

template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);
인자로 주어지는 first 와 last iterator 사이를 순환하며, 중복되는 값을 가지는 원소가 있을경우 처음 원소만 그대로 두고 그뒤에 오는 원소들을 모두 삭제한다. 
#include <algorithm>
#include <vector>

int main()
{
    vector<int> V;
    V.push_back(3);
    V.push_back(6);
    V.push_back(1);
    V.push_back(2);
    V.push_back(2);
    V.push_back(1);
    V.push_back(3);


	sort(V.begin(). V.end());
    copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));

    cout << endl;
	// 1 1 2 2 3 3 6 이 출력된다. 

    vector<int>::iterator new_end = unique(V.begin(), V.end());
    copy(V.begin(), new_end, ostream_iterator<int>(cout, " "));
    cout << endl;
	// 1 2 3 6 이 출력된다. 
}

2.3절. Sorting 알고리즘들

제목에 현혹되지 말기바란다. 컨테이너에 포함된 원소를 정렬하는 그런 알고리즘들을 뜻하는게 아니다. 여기에서 말하는 Sorting 이란 원소가 미리 정렬되어있는 을 뜻한다. 여기에서 소개될 알고리즘들을 제대로 사용하기 위해서는 각 컨테이너의 원소가 미리 소팅되어 있어야만 제대로된 결과를 얻을수 있기 때문이다.(sort 알고리즘은 제외)

2.3.1절. sort

가장 간단하며 가장 자주 사용되는 알고리즘이다. 

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
          StrictWeakOrdering comp);
인자로 주어지는 first 와 last 이터레이터 사이를 순환하면서 소팅한다.

그런데 그 밑에 있는 오버로딩된 또다른 sort 버젼의 경우 comp 가 추가로 들어가는것을 알수 있다. 이것은 함수객체로써, 비교를 위한 함수를 사용하고자 할때 사용된다. 예를들어서 컨테이너에 들어있는 타입이 int 이거나, string 일경우에는 비교연산이 되므로 굳이 comp 함수객체를 필요로 하지 않을것이다. 그러나 char * 같은경우에는 비교연산이 되지 않으므로, 이럴경우에는 별도의 비교연산을 위한 함수객체가 필요하다. 

#include <algorithm>
#include <vector>
#include <string>

bool case_eq(char *c1,  char *c2) 
{ 
    if (strcmp(c1, c2) < 0)
        return 1;
    else
        return 0;
} 
int main()
{
    vector<int> V;
    V.push_back(4);
    V.push_back(7);
    V.push_back(2);
    V.push_back(3);
    V.push_back(1);
    V.push_back(6);

    sort(V.begin(), V.end());
    copy(V.begin(), V.end(), ostream_iterator<int>(cout, "\n")); 

    vector<char *> V2;
    V2.push_back("my name");
    V2.push_back("hello");
    V2.push_back("ma name");
    V2.push_back("hael");

    // 만약 case_eq 함수객체를 사용하지 않는다면 sort 되지 않을것이다. 
    sort(V2.begin(), V2.end(), case_eq);
    copy(V2.begin(), V2.end(), ostream_iterator<char *>(cout, "\n")); 
}
위의 예제를 보면 함수객체가 어떻게 사용되는지 알수 있을것이다. 이 함수객체를 약간만 수정하면 소팅을 역으로 할수도 있다. 단지 strcmp(c1, c2) < 0 을 strcmp(c1, c2) > 0 으로만 바꿔주면 된다.

2.3.2절. lower_bound 와 upper_bound

이름에서 알수 있듯이 이것들은 컨테이너에서 원하는 요소와 연속적으로 일치하는 첫번째 위치와 마지막 위치를 알아내기 위해서 사용한다. STL 의 컨테이너를 공부했다면 multimap 이나 multiset 에 같은이름의 함수를 본적이 있을것이다. 이들과 같은 일을한다. 

#include <vector>
#include <algorithm>

int main()
{
    vector<int> V;
    V.push_back(1);
    V.push_back(1);
    V.push_back(2);
    V.push_back(2);
    V.push_back(2);
    V.push_back(3);
    V.push_back(4);
    V.push_back(5);
    V.push_back(2);

    vector<int>::iterator m_start = lower_bound(V.begin(), V.end(), 2);
    vector<int>::iterator m_end   = upper_bound(V.begin(), V.end(), 2);

    copy(m_start, m_end, ostream_iterator<int>(cout, " "));
    // 2 2 2  가 출력될것이다.  
    // 마지막의 2는 연속된 값이 아님으로 무시된다.  
}

2.3.3절. merge

2개의 컨테이너의 원소를 결합한다. 컨테이너의 원소들은 결합되면서 자동적으로 sort 된다. 만약 원소가 비교연산을 지원하지 않는 타입의 원소라면 비교객체 함수를 정의해서 사용하면 된다. 이외에도 함수객체는 알고리즘의 연산을 방식을 변경하기 위한 용도로도 사용된다. 이 알고리즘을 적용하기 위해서는 각 컨테이너의 원소가 미리 정렬되어 있어야 한다. 

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result, StrictWeakOrdering comp);
merge 된후의 값은 result 로 출력가능하다. 
#include <vector>
#include <algorithm>

int main()
{
    vector<int> V1;
    vector<int> V2;

    V1.push_back(1);
    V1.push_back(3);
    V1.push_back(5);

    V2.push_back(2);
    V2.push_back(4);
    V2.push_back(5);
    V2.push_back(6);

    merge(V1.begin(), V1.end(), V2.begin(), V2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
}
만약 원소가 비교연산이 불가능한 char * 과 같은 형일경우에는 객체함수 comp 를 정의하면 된다. 정의 방법인 이전에 이미 설명했음으로 그냥 넘어가도록 하겠다.

2.3.4절. set_union, set_intersection, set_difference

각각 합집합, 교집합, 차집합을 구현하는 알고리즘이다. 때에 따라서 매우 유용하게 사용할수 있을것이다. 

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class StrictWeakOrdering>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result, 
                         StrictWeakOrdering comp);
set_union 알고리즘만 출력했는데, 다른것들역시 이름만 다르고 동일하게 사용할수 있다. 비교객체 함수인 comp 를 정의함으로써, 결과값을 sort 할수있다. comp 를 이용해서 알고리즘의 연산방식을 변경시켜줄수 있다.

또한 컨테이너에 입력되어 있는 원소들은 미리 sort 되어 있어야 한다. 

#include <algorithm>
#include <vector>

int main()
{
    vector<int> V1, V2;

    V1.push_back(1);
    V1.push_back(2);
    V1.push_back(3);
    V1.push_back(4);
    V1.push_back(7);

    V2.push_back(0);
    V2.push_back(1);
    V2.push_back(7);
    V2.push_back(8);
    V2.push_back(9);


    set_union(V1.begin(), V1.end(), V2.begin(), V2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    // 0 1 2 3 4 7 8 9 

    set_intersection(V1.begin(), V1.end(), V2.begin(), V2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    // 1 7 이 출력된다. 

    set_difference(V1.begin(), V1.end(), V2.begin(), V2.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    // 2 3 4 이 출력된다. 
}

2.4절. Generalized numeric algorithms

이번에는 수치알고리즘에 대해서 알아보도록 하겠다. 이들 수치 알고리즘을 사용하기 위해서는 numeric 를 include 시켜야 한다.

2.4.1절. accumulate

컨테이너의 모든 원소를 더하기 위해서 사용한다. 

template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);

template <class InputIterator, class T, class BinaryFunction>
T accumulate(InputIterator first, InputIterator last, T init,
             BinaryFunction binary_op);
첫번째와 두번째 인자는 알고리즘을 적용할 원소의 범위를 지정하기 위한 이터레이터 이며, 세번째 아규먼트는 초기값이다. 또한 다른 많은 알고리즘과 마찬가지로 함수 객체를 이용해서 알고리즘의 연산방식을 변경시킬수도 있다. 
#include <numeric>
#include <vector>

int mysum(int a, int b)
{
    return a * b;
}

int main()
{
    vector<int> V;

    V.push_back(1);
    V.push_back(2);
    V.push_back(3);
    V.push_back(4);
    V.push_back(5);
    V.push_back(6);
    V.push_back(7);

    cout << accumulate(V.begin(), V.end(), 0) << endl;
    // 120
    cout << accumulate(V.begin(), V.end(), 1, mysum) << endl;
    // 5040
}
2번째 accumulate 를 적용시킬때는 mysum 이라는 함수 객체를 이용해서 기존의 '+' 연산을 '*' 연산을 하도록 변경했음을 알수 있다.

2.4.2절. partical_sum

partical_sum 은 x0, x0 + x1, x0 + x1 + x3 과 같은 연산을 할때 사용한다. 

template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result);

template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator partial_sum(InputIterator first, InputIterator last,
                           OutputIterator result, BinaryOperation binary_op);
첫번째와 두번째 아규먼트는 컨테이너에서 알고리즘을 적용할 구간의 iterator 값이다. 다른 알고리즘과 마찬가지로 함수객체를 이용해서 알고리즘의 연산을 변경할수 있다. 
#include <numeric>
#include <vector>
#include <algorithm>

int mysum(int a, int b)
{
    return a * b;
}

int main()
{
    vector<int> V;

    V.push_back(1);
    V.push_back(2);
    V.push_back(3);
    V.push_back(4);
    V.push_back(5);

    partial_sum(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    
    partial_sum(V.begin(), V.end(), ostream_iterator<int>(cout, " "), mysum);
    cout << endl;
}
첫번째 partial_sum 은 1, 1+2, 1+2+3, 1+2+3+4 .. 의 연산을 수행할것이다. 반면 두번째 연산은 함수객체에 의해서 1, 1*2, 1*2*3, 1*2*3 .. 의 연산을 수행하게 될것이다.

2.4.3절. adjacent_difference

이것은 x0, x1 - x0, x2 - x1.. 과 같이 인접한 두원소의 차를 구한다. 

template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last, 
                                   OutputIterator result);

template <class InputIterator, class OutputIterator, class BinaryFunction>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
                                   OutputIterator result,
                                   BinaryFunction binary_op);
역시 구간을 정하기 위한 2개의 iterator 가 사용되며, 알고리즘의 연산을 변경하기 위한 함수객체가 사용되기도 한다. 
	
#include <numeric>
#include <vector>

int mysum(int a, int b)
{
    return a * b;
}

int main()
{
    vector<int> V;

    V.push_back(1);
    V.push_back(2);
    V.push_back(3);
    V.push_back(4);
    V.push_back(5);

    adjacent_difference(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    adjacent_difference(V.begin(), V.end(), ostream_iterator<int>(cout, " "), mysum);
    cout << endl;
}

2.4.4절. inner_product

이것은 두개의 컨테이너의 원소들의 내적을 구하고자 할때 사용된다. 즉 A 와 B 컨테이너의 내적을 구한다면 A0 X B0 + A1 X B1 + ... An X Bn 공식을 따르게 될것이다. 

Inner_product is an overloaded name; there are actually two inner_product functions. 
template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init);

template <class InputIterator1, class InputIterator2, class T,
          class BinaryFunction1, class BinaryFunction2>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init, BinaryFunction1 binary_op1,
                BinaryFunction2 binary_op2);
				
#include <numeric>
#include <vector>
#include <algorithm>

int mysum(int a, int b)
{
    return a * b;
}

int main()
{
    vector<int> V1;
    vector<int> V2;

    V1.push_back(1);
    V1.push_back(2);
    V1.push_back(3);
    V1.push_back(4);

    V2.push_back(5);
    V2.push_back(6);
    V2.push_back(7);
    V2.push_back(8);
    V2.push_back(9);

    cout << inner_product(V1.begin(), V1.end(), V2.begin(), 0) << endl;
}
위의 결과값은 1*5+2*6+3*7+4*8 = 70 이 될것이다.

Email을 기입하면, 댓글이 메일로 전달됩니다.