About STL : C++ STL 프로그래밍(10)-알고리즘2

한빛미디어

2009-11-19

by HANBIT

47,710

제공 : 한빛 네트워크
저자 : 최흥배
이전기사 :

이전 회에는 STL 알고리즘들 중 비슷한 성격의 알고리즘을 모아서 "변경 불가 시퀀스 알고리즘", "변경 가능 시퀀스 알고리즘", "정렬 관련 알고리즘", "범용 수치 알고리즘"으로 크게 네 개로 나누고 이중 "변경 불가 시퀀스 알고리즘" 과 "변경 가능 시퀀스 알고리즘"에 있는 주요 알고리즘의 특징과 사용 방법에 대해서 설명하였습니다.

이번 회는 이전 회에 설명하지 못한 "정렬 관련 알고리즘" 과 "범용 수치 알고리즘"의 주요 알고리즘의 특징과 사용 방법에 대해서 설명하겠습니다.

10.1. 정렬 관련 알고리즘

10.1.1 sort

sort는 컨테이너에 있는 데이터들을 내림차순 또는 오름차순으로 정렬 할 때 가장 자주 사용하는 알고리즘입니다. 컨테이너에 저장하는 데이터의 자료 형이 기본형이라면 STL에 있는 greate나 less 비교 조건자를 사용합니다(STL의 string의 정렬에도 사용할 수 있습니다. 다만 이 때는 알파벳 순서로 정렬합니다). 기본형이 아닌 경우에는 직접 비교 조건자를 만들어서 사용해야 합니다.

sort의 원형

template
   void sort( RandomAccessIterator _First, RandomAccessIterator _Last );

첫 번째와 두 번째 파라미터는 정렬하려는 구간의 시작과 마지막을 가리키는 반복자입니다. 비교 조건자를 필요로 하지 않고 기본형을 저장한 컨테이너를 오름차순으로 정렬합니다.

template
   void sort( RandomAccessIterator _First, RandomAccessIterator _Last, BinaryPredicate _Comp );

첫 번째와 두 번째 파라미터는 정렬하려는 구간의 시작과 마지막을 가리키는 반복자입니다. 세 번째 파라미터는 정렬 방법을 기술한 비교 조건자입니다.

sort 알고리즘의 원형을 보면 알 수 있듯이 램덤 접근 반복자를 지원하는 컨테이너만 sort 알고리즘을 사용할 수 있습니다.

sort 사용 방법

vector vec1;
…..
// 오름차순 정렬
sort( vec1.begin(), vec1.end() );

// 내림차순 정렬
Sort( vec1.begin(), vec1.end(), greater() );

< 리스트 1. less와 greater 비교 조건자를 사용한 sort >

#include 
#include 
#include 
#include 

using namespace std;

int main()
{
  vector vec1(10);
  vector vec2(10);
  vector vec3(10);
  vector ::iterator Iter1;

  generate( vec1.begin(), vec1.end(), rand );
  generate( vec2.begin(), vec2.end(), rand );
  generate( vec3.begin(), vec3.end(), rand );

  // 오름차순 정렬
  cout << "vec1 정렬 하기 전" << endl;
  for( Iter1 = vec1.begin(); Iter1 != vec1.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;

  sort( vec1.begin(), vec1.end() );
  
  cout << "vec1 오름차순 정렬" << endl;
    for( Iter1 = vec1.begin(); Iter1 != vec1.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;
  cout << endl;

  // 내림차순 정렬
  cout << "vec2 정렬 하기 전" << endl;
  for( Iter1 = vec2.begin(); Iter1 != vec2.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;
  
  sort( vec2.begin(), vec2.end(), greater() );

  cout << "vec2 내림차순 정렬" << endl;
    for( Iter1 = vec2.begin(); Iter1 != vec2.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;
  cout << endl;

  // 일부만 내림차순 정렬
  cout << "vec3 정렬 하기 전" << endl;
  for( Iter1 = vec3.begin(); Iter1 != vec3.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;

  sort( vec3.begin() + 5, vec3.end(), greater() );

  cout << "vec3 일부만 내림차순 정렬" << endl;
    for( Iter1 = vec3.begin(); Iter1 != vec3.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;

  return 0;
}

< 결과 >

<리스트 1>은 기본 형 데이터를 정렬하는 예제로 이번에는 유저 정의 형 데이터를 정렬하는 예제를 보여 드리겠습니다.

< 리스트 2. USER 구조체의 Money를 기준으로 정렬 >

#include 
#include 
#include 
#include 

using namespace std;

struct USER
{
  int UID;
  int Level;
  int Money;
};

struct USER_MONEY_COMP
{
  bool operator()(onst USER& user1, const USER& user2)
  {
    return user1.Money > user2.Money;
  }
};

int main()
{
  USER User1; User1.UID = 1;  User1.Money = 2000;
  USER User2; User2.UID = 2;  User2.Money = 2050;
  USER User3; User3.UID = 3;  User3.Money = 2200;
  USER User4; User4.UID = 4;  User4.Money = 1000;
  USER User5; User5.UID = 5;  User5.Money = 2030;

  vector Users;
  Users.push_back( User1 );  Users.push_back( User2 );
  Users.push_back( User3 );  Users.push_back( User4 );
  Users.push_back( User5 );

  vector ::iterator Iter1;

  cout << "돈을 기준으로 정렬 하기 전" << endl;
  for( Iter1 = Users.begin(); Iter1 != Users.end(); ++Iter1 ) {
    cout << Iter1->UID << " : " << Iter1->Money << ", ";
  }
  cout << endl << endl;

  sort( Users.begin(), Users.end(), USER_MONEY_COMP() );

  cout << "돈을 기준으로 내림차순으로 정렬" << endl;
  for( Iter1 = Users.begin(); Iter1 != Users.end(); ++Iter1 ) {
    cout << Iter1->UID << " : " << Iter1->Money << ", ";
  }
  cout << endl << endl;

  return 0;
}

< 결과 >

10.1.2. binary_search

이미 정렬 되어 있는 것 중에서 특정 데이터가 지정한 구간에 있는지 조사하는 알고리즘입니다. 이것도 sort와 같이 비교 조건자가 필요 없는 버전과 필요한 버전 두 개가 있습니다(단 sort와 다르게 랜덤 접근 반복자가 없는 컨테이너도 사용할 수 있습니다).

binary_search 원형

template
   bool binary_search( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );

template
   bool binary_search( ForwardIterator _First, ForwardIterator _Last, const Type& _Val, 
                        BinaryPredicate _Comp );

binary_search 사용 방법

vector vec1;
…..
sort( vec1.beign(), vec1.end() );
…...
bool bFind = binary_search( vec1.begin(), vec1.end(), 10 );

binary_search는 정렬한 이후에 사용해야 한다고 앞서 이야기 했습니다. 만약 정렬하지 않고 사용하면 어떻게 될까요?

< 리스트 3. 정렬하지 않고 binary_search 사용 >

int main()
{
  vector vec1;
  vec1.push_back(10);  vec1.push_back(20);  vec1.push_back(15);
  vec1.push_back(7);  vec1.push_back(100); vec1.push_back(40);
  vec1.push_back(11);  vec1.push_back(60);  vec1.push_back(140);

  bool bFind = binary_search( vec1.begin(), vec1.begin() + 5, 15 );
  if( false == bFind ) {
    cout << "15를 찾지 못했습니다." << endl;
  } else {
    cout << "15를 찾았습니다." << endl;
  }

  return 0;
}

디버그 모드로 빌드 후 실행 하면 아래와 같은 에러 창이 나옵니다.

그림3

에러 내용은 시퀀스가 정렬되지 않았다고 나옵니다. 릴리즈 모드 빌드 후 실행하면 위와 같은 에러는 나오지 않지만 결과는 false가 나옵니다.

binary_search를 사용할 때는 꼭 먼저 정렬해야 한다는 것을 잊지 말기를 바랍니다.

< 리스트 4. 정렬 후 binary_search 사용 >

#include 
#include 
#include 
#include 

using namespace std;

int main()
{
  vector vec1;
  vec1.push_back(10);  vec1.push_back(20);  vec1.push_back(15);
  vec1.push_back(7);  vec1.push_back(100); vec1.push_back(40);
  vec1.push_back(11);  vec1.push_back(60);  vec1.push_back(140);

  sort( vec1.begin(), vec1.end() );

  bool bFind = binary_search( vec1.begin(), vec1.begin() + 5, 15 );
  if( false == bFind ) {
    cout << "15를 찾지 못했습니다." << endl;
  } else {
    cout << "15를 찾았습니다." << endl;
  }

  return 0;
}

< 결과 >

비교 조건자를 사용하는 경우는 위의 <리스트 2> 코드를 예를들면 <리스트 2>에서 사용했던 USER_MONEY_COMP 조건자를 사용합니다.

< 리스트 4. 리스트 2의 Users를 binary_search에 사용 >

…….
sort( Users.begin(), Users.end(), USER_MONY_COMP() );
bool bFind = binary_search( Users.begin(), Users.begin() + 3, User5, USER_MONY_COMP() );
…….

10.1.3 merge

두 개의 정렬된 구간을 합칠 때 사용하는 것으로 두 구간과 겹치지 않은 곳에 합친 결과를 넣어야 합니다. 주의해야 할 점은 합치기 전에 이미 정렬이 되어 있어야 하며 합친 결과를 넣는 것은 합치는 것들과 겹치면 안되며, 또한 합친 결과를 넣을 수 있는 공간을 확보하고 있어야 합니다.

merge의 원형

template
   OutputIterator merge( InputIterator1 _First1, InputIterator1 _Last1,
      InputIterator2 _First2, InputIterator2 _Last2, OutputIterator _Result
   );

template
   OutputIterator merge( InputIterator1 _First1, InputIterator1 _Last1,
    InputIterator2 _First2, InputIterator2 _Last2, OutputIterator _Result, BinaryPredicate _Comp );

merge 사용 방법

vector vec1, vec2, vec3;
…..
merge( vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin() );

아래의 <리스트 5>는 vec1과 vec2를 합쳐서 vec3에 넣는 것으로 vec1과 vec2는 이미 정렬되어 있고 vec3는 이 vec1과 vec2의 크기만큼의 공간을 미리 확보해 놓고 있습니다.

< 리스트 5. 두 개의 vector의 merge >

#include 
#include 
#include 
#include 

using namespace std;

int main()
{
  vector ::iterator Iter1;
  vector vec1,vec2,vec3(12);
  
  for( int i = 0; i < 6; ++i )
    vec1.push_back( i );

  for( int i = 4; i < 10; ++i )
    vec2.push_back( i );
  
  cout << "vec1에 있는 값" << endl;
  for( Iter1 = vec1.begin(); Iter1 != vec1.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;

  cout << "vec2에 있는 값" << endl;
  for( Iter1 = vec2.begin(); Iter1 != vec2.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;


  merge( vec1.begin(), vec1.end(), 
      vec2.begin(), vec2.end(), 
      vec3.begin() );

  cout << "vec1과 vec2를 merge한 vec3에 있는 값" << endl;
  for( Iter1 = vec3.begin(); Iter1 != vec3.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;

  return 0;
}

< 결과 >

정렬 관련 알고리즘은 위에 소개한 세 개 이외에도 더 있지만 지면 관계상 보통 자주 사용하는 sort, binary_search, merge 세 개를 소개하는 것으로 마칩니다. 제가 소개하지 않은 정렬 관련 알고리즘을 더 공부하고 싶은 분들은 MSDN이나 C++ 책을 통해서 공부하시기를 바랍니다.

10.2. 범용 수치 알고리즘

10.2.1 accumulate

지정한 구간에 속한 값들을 모든 더한 값을 계산합니다. 기본적으로 더하기 연산만 하지만 조건자를 사용하면 더하기 이외의 연산도 할 수 있습니다. accumulate를 사용하기 위해서는 앞서 소개한 알고리즘과 다르게 헤더 파일을 포함해야 합니다.

accumulate의 원형

template
   Type accumulate( InputIterator _First, InputIterator _Last, Type _Val );

첫 번째와 두 번째 파라미터는 구간이며, 세 번째 파라미터는 구간에 있는 값에 더할 값입니다.

template
 Type accumulate( InputIterator _First, InputIterator _Last, Type _Val, BinaryOperation _Binary_op );

네 번째 파라미터는 조건자로 조건자를 사용하여 기본 자료 형 이외의 데이터를 더할 수 있고, 더하기 연산이 아닌 다른 연산을 할 수도 있습니다.

accumulate 사용 방법

vector vec1;
…..
// vec1에 있는 값들만 더 한다.
int Result = accmulate( vec1.begin(), vec1.end(), 0, );

아래의 <리스트 6>은 int를 저장하는 vector를 대상으로 accmurate를 사용하는 가장 일반적인 예입니다.

< 리스트 6. vector에 있는 값들을 계산 >

#include 
#include 
#include 

using namespace std;

int main()
{
  vector ::iterator Iter1;
  vector vec1;

  for( int i = 1; i < 5; ++i )
    vec1.push_back( i );

  // vec1에 있는 값
  for( Iter1 = vec1.begin(); Iter1 != vec1.end(); ++Iter1 ) {
    cout << *Iter1 << ", ";
  }
  cout << endl;


  // vec1에 있는 값들을 더한다.
  int Result1 = accumulate( vec1.begin(), vec1.end(), 0 );
  // vec1에 있는 값들을 더한 후 10을 더 한다.
  int Result2 = accumulate( vec1.begin(), vec1.end(), 10 );

  cout << Result1 << ", " << Result2 << endl;
}

< 결과 >

이번에는 조건자를 사용하여 유저 정의형을 저장한 vector를 accmulate에서 사용해 보겠습니다. 이번에도 더하기 연산만을 했지만 조건자를 사용하면 곱하기 연산 등도 할 수 있습니다.

< 리스트 7. 조건자를 사용한 accumulate >

#include 
#include 
#include 

using namespace std;

struct USER
{
  int UID;
  int Level;
  int Money;
};

struct USER_MONY_ADD
{
  USER operator()(const USER& user1, const USER& user2)
  {
    USER User;
    User.Money = user1.Money + user2.Money;
    return User;
  }
};

int main()
{
  USER User1; User1.UID = 1;  User1.Money = 2000;
  USER User2; User2.UID = 2;  User2.Money = 2050;
  USER User3; User3.UID = 3;  User3.Money = 2200;
  USER User4; User4.UID = 4;  User4.Money = 1000;
  USER User5; User5.UID = 5;  User5.Money = 2030;

  vector Users;
  Users.push_back( User1 );  Users.push_back( User2 );
  Users.push_back( User3 );  Users.push_back( User4 );
  Users.push_back( User5 );

  vector ::iterator Iter1;

  for( Iter1 = Users.begin(); Iter1 != Users.end(); ++Iter1 ) {
    cout << Iter1->UID << " : " << Iter1->Money << ", ";
  }
  cout << endl << endl;

  // Users에 있는 Money 값만 더하기 위해 Money가 0인 InitUser를 세 번째 파라미터에
  // 조건자를 네 번째 파라미터로 넘겼습니다.
  USER InitUser; InitUser.Money = 0;
  USER Result = accumulate( Users.begin(), Users.end(), InitUser, USER_MONY_ADD() );
  cout << Result.Money << endl;
}

< 결과 >

10.2.2 inner_product

두 입력 시퀀스의 내적을 계산하는 알고리즘으로 기본적으로는 +와 *을 사용합니다. 두 입력 시퀀스의 값은 위치의 값을 서로 곱한 값을 모두 더 한 것이 최종 계산 값이 됩니다. 주의 해야 할 것은 두 입력 시퀀스의 구간 중 두 번째 시퀀스는 첫 번째 시퀀스 구간 보다 크거나 같아야 합니다. 즉 첫 번째 시퀀스 구간의 데이터는 5개가 있는데 두 번째 시퀀스에 있는 데이터가 5개 보다 작으면 안됩니다.

inner_product의 원형

template
   Type inner_product( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, 
      Type _Val );

조건자를 사용하는 버전으로 조건자를 사용하면 유저 정의형을 사용할 수 있는 내적 연산 방법을 바꿀 수 있습니다.

template
   Type inner_product( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, 
      Type _Val, BinaryOperation1 _Binary_op1, BinaryOperation2 _Binary_op2 );

아래의 <리스트 8>은 조건자를 사용하지 않는 inner_product를 사용하는 것으로 vec1과 vec2의 내적을 계산합니다.

< 리스트 8. inner_product를 사용하여 내적 계산 >

#include 
#include 
#include 

using namespace std;

int main()
{
  vector vec1;
  for( int i = 1; i < 4; ++i )
    vec1.push_back(i);

  vector vec2;
  for( int i = 1; i < 4; ++i )
    vec2.push_back(i);

  int Result = inner_product( vec1.begin(), vec1.end(), vec2.begin(), 0 );
  cout << Result << endl;

  return 0;
}

< 결과 >

<리스트 8>의 vec1과 vec2에는 각각 1, 2, 3 의 값이 들어가 있습니다. 이것을 네 번째 파라미터의 추가 값을 0을 넘긴 inner_droduct로 계산하면

14 = 0 + (1 * 1) + (2 * 2) + (3 * 3);

가 됩니다.

<리스트 8>의 코드를 보기 전에는 어떻게 계산 되는지 잘 이해가 되지 않는 분들은 <리스트 8> 코드를 보면 inner_product가 어떻게 계산 되는지 쉽게 이해할 수 있을 것입니다.

inner_product도 다른 알고리즘처럼 조건자를 사용할 수 있습니다. 제가 앞서 다른 알고리즘에서 조건자를 사용한 예를 보여 드렸으니 inner_product에서 조건자를 사용하는 방법은 숙제로 남겨 놓겠습니다.^^

범용 수치 알고리즘에는 위에 설명한 accmulate와 inner_product 이외에도 더 있지만 다른 것들은 보통 사용 빈도가 높지 않고 그것들을 다 소개하기에는 많은 지면이 필요로 하므로 이것으로 끝내겠습니다.^^;

범용 수치 알고리즘을 끝으로 STL의 알고리즘을 설명하는 것을 마치겠습니다. 이전 회와 이번에 걸쳐서 소개한 알고리즘은 STL에 있는 알고리즘 중 사용 빈도가 높은 알고리즘들로 이 것 이외에도 많은 알고리즘이 있으니 제가 설명한 알고리즘을 공부한 후에는 제가 설명하지 않은 알고리즘들도 공부하시기를 바랍니다.

지금까지 제가 설명한 글들을 보시면 STL은 사용할 때 일관성이 높다라는 것을 알 수 있을 것입니다. 높은 일관성 덕분에 하나를 알면 그 다음은 더 쉽게 알 수 있습니다.

C++의 STL은 결코 사용하기 어려운 것이 아닙니다. C++을 알고 있다면 아주 쉽게 공부할 수 있으며 STL을 사용함으로 더 쉽고 견고하게 프로그래밍할 수 있습니다. 그러나 STL의 컨테이너나 알고리즘에 대해서 잘 모르면서 다른 사람들이 사용한 코드를 보고 그냥 사용하면 STL이 독이 될 수도 있음을 조심해야 합니다.

저는 몇 달 전부터 C++0x을 공부하고 있습니다. C++0x는 현재 개발중인 새로운 C++ 표준입니다. C++0x에는 지금의 C++을 더 강력하고 쉽게 사용할 수 있게 해 주는 다양한 것들이 있습니다. 이 중 lambda라는 것이 있는데 이것을 사용하면 알고리즘에서 조건자를 사용할 때 지금보다 훨씬 더 편하게 기술할 수 있습니다. STL을 공부한 이 후에는 C++0x을 공부하시기를 바랍니다.

TAG :

이전 글 : About STL : C++ STL 프로그래밍(9)-알고리즘1

다음 글 : 웹 스퀘어드 : 5년 간의 Web 2.0의 행적

최신 콘텐츠

한빛출판네트워크

인기 검색어 (최근 1개월간)

책

강의/세미나

채널.H

IT/모바일

About STL : C++ STL 프로그래밍(10)-알고리즘2

최근 본 상품0