37-2-다.알고리즘

STL의 알고리즘 함수들은 대부분 특정 컨테이너의 멤버 함수가 아닌 일반 전역 함수로 작성되어 있다. 왜냐하면 반복자에 의해 컨테이너를 다루는 방법이 일반화되어 모든 컨테이너에 대해 적용할 수 있으므로 멤버 함수가 될 필요도 없고 멤버 함수가 되어서도 안된다. STL은 일반화된 알고리즘을 제공하므로 캡슐화를 적극적으로 사용하지 않는다. 컨테이너 클래스들은 표현하고자 하는 자료 구조를 위한 데이터 멤버와 연산자만을 정의하며 알고리즘 구현은 반복자와 전역 함수에게 맡긴다.

알고리즘 함수들은 대부분 algorithm 헤더 파일에 정의되어 있으므로 알고리즘 함수 중 하나라도 사용하려면 이 헤더 파일을 포함해야 한다. 예상할 수 있겠지만 이 헤더 파일에는 STL의 모든 알고리즘이 정의되어 있으므로 굉장히 길이가 길다. 시간이 허락한다면 한 번쯤 들여다 볼만한 헤더 파일이다. 알고리즘 함수 중 가장 흔하게 사용되는 것은 컨테이너에 특정값이 존재하는지를 찾는 find 이다. 원형은 다음과 같다.

 

template<typename InIt, class T>

 InIt find(InIt first, InIt last, const T& val);

 

임의의 모든 타입에 대해 동작할 수 있어야 하므로 STL 알고리즘 함수들은 예외없이 템플릿으로 구현되어 있다. find의 경우 검색중에 사용할 반복자와 컨테이너의 요소 타입을 템플릿 인수로 받아들여 구체화된다. 그래서 벡터든 리스트든 해당 컨테이너의 반복자만 전달하면 되고 요소가 정수형이든 Time이나 Person이든 가리지 않고 검색을 할 수 있는 것이다. 템플릿으로 전달되는 인수는 InIt, OutIt, T 등의 이름으로 일관되게 표시되므로 이후 알고리즘 함수를 소개할 때 template문은 생략하기로 한다.

find는 first ~ last 사이의 반복자 구간에서 T형의 값 val이 있는지 검사한다. 발견되면 해당 위치의 반복자가 리턴되며 발견되지 않을 경우 컨테이너 전체를 순회만 하고 종료되므로 구간의 끝인 last가 리턴된다. C 함수들은 검색에 실패할 경우 NULL을 리턴하지만 STL은 검색 실패조차도 반복자로 리턴한다.

반복자만으로 요소를 읽을 수 있고 이 요소를 val과 비교할 수 있으며 비교 범위도 명확하게 전달되었으므로 find가 컨테이너에 대한 정보를 전달받을 필요는 없다. 컨테이너가 어떤 식의 구조를 가지는지 모르므로 find는 가장 간단하고 어떤 형태의 자료에나 사용할 수 있는 순차 검색 방법을 사용한다. 예제를 작성해 보자.

 

예 제 : find

#include <iostream>

#include <vector>

#include <list>

#include <algorithm>

using namespace std;

 

void main()

{

     int ari[]={1,2,3,4,5};

     vector<int> vi(&ari[0],&ari[5]);

     list<int> li(&ari[0],&ari[5]);

 

     puts(find(vi.begin(),vi.end(),4)==vi.end() ? "없다.":"있다.");

     puts(find(li.begin(),li.end(),8)==li.end() ? "없다.":"있다.");

     puts(find(&ari[0],&ari[5],3)==&ari[5] ? "없다.":"있다.");

}

 

벡터와 리스트, 단순 배열에 대해 find로 여러 가지 값들을 검색해 보았다. 크기가 작은 컨테이너라 결과가 뻔히 보인다.

 

있다.

없다.

있다.

 

컨테이너에 상관없이 검색 방법이 똑같다는 것을 알 수 있다. 검색 범위를 지정하는 반복자와 찾고자 하는 값만 인수로 전달하는데 예제에서는 컨테이너 전체 범위에 대해 정수값을 검색했다. 컨테이너의 내부 구조가 달라도 반복자에 의해 읽고 다음 요소로 이동할 수 있기 때문에 똑같은 알고리즘 함수를 사용할 수 있는 것이다. algorithm 헤더 파일을 뒤져 보면 다음처럼 정의되어 있는 find 함수를 볼 수 있다.

 

InIt find(InIt first, InIt last, const T& val)

{

     for (;first != last; ++first) {

          if (*first == val) break;

     }

     return first;

}

 

first를 계속 증가시키면서 last에 이를 때까지 순회하며 순회 중에 *연산자로 first의 값을 읽어 val과 같은지를 점검한다. 검색되었다면 이 상태에서 루프를 빠져 나와 first를 리턴하며 검색에 실패했다면 first가 last까지 이동한 채로 리턴될 것이다. 알고리즘의 실제 구현은 컴파일러마다 조금씩 다른데 위 코드는 비주얼 C++의 것이고 gcc는 find를 다음과 같이 구현하고 있다.

 

InIt find(InIt first, InIt last, const T& val)

{

     while(first != last && *first != val) ++first;

     return first;

}

 

끝에 도달하거나 검색하는 값을 찾을 때까지 무조건 전진 이동하다가 루프가 끝났을 때의 반복자를 리턴한다. 두 구현의 코드는 조금 다르지만 하는 일은 사실상 동일하다고 할 수 있다. 알고리즘이 어떻게 구현되어 있든지 알고리즘 본체에서 사용하는 ++, !=, * 연산자를 모든 반복자가 지원하므로 검색 알고리즘이 획일적으로 정의된다. 다른 알고리즘도 원리는 동일한데 내부가 궁금하면 항상 헤더 파일을 읽어 보도록 하자.

검색 다음으로 많이 사용되는 알고리즘은 자료를 일정한 기준에 따라 재배치하는 정렬이다. 컨테이너내의 모든 요소들을 여러 번 비교하고 결과에 따라 요소를 교환하는 과정을 정렬 완료될 때까지 반복해야 하는 꽤 복잡한 연산이다. 이런 연산도 sort 함수 하나만 사용하면 쉽게 수행할 수 있다. sort의 원형은 다음과 같다.

 

void sort(RanIt first, RanIt last);

 

이 함수는 인수로 주어진 first ~ last 사이의 모든 요소를 정렬한다. 정렬을 하기 위해서는 객체들을 비교해야 하는데 sort 함수는 정렬 중에 < 연산자로 요소의 순위를 판단한다. 따라서 정렬 대상 요소들은 < 연산자를 반드시 정의해야 한다. 정수, 실수 등의 기본 타입은 < 연산자로 비교할 수 있으므로 항상 정렬 가능하며 사용자가 정의한 클래스라도 < 연산자가 오버로딩되어 있으면 이 함수로 정렬 가능하다.

 

예 제 : sort

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

void main()

{

     int ari[]={2,8,5,1,9};

     vector<int> vi(&ari[0],&ari[5]);

 

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

     vector<int>::iterator it;

     for (it=vi.begin();it!=vi.end();it++) {

          printf("%d\n",*it);

     }

}

 

벡터에 다섯 개의 정수를 넣어 두고 sort 함수로 정렬한 후 출력해 보았다. 오름차순으로 정렬되어 출력될 것이다.

 

1

2

5

8

9

 

정렬은 워낙 흔한 연산이라 굉장히 많은 알고리즘이 개발되어 있다. STL의 sort 함수는 그 중 가장 빠르다고 정평이 난 퀵 소트 알고리즘을 사용하는데 앞에서 공부해 봐서 알겠지만 퀵 소트 알고리즘은 그다지 간단하지 않다. 이런 알고리즘을 범위만 전달하면 공짜로 쓸 수 있다는 것이 STL의 매력이다. 가장 기본적인 두 개의 알고리즘에 대해 예제를 만들어 봤는데 몇 가지만 더 구경해 보자.

 

void reverse(BiIt first, BiIt last);

 

reverse 함수는 이름대로 지정한 구간의 요소들 순서를 반대로 뒤집는다. begin과 end를 구간으로 지정하면 컨테이너의 모든 요소들 순서가 반대로 바뀔 것이다. 컨테이너의 일부 구간만 반대로 뒤집을 수도 있다. 다음 예제는 배열의 중간 부분 요소들을 반대의 순서로 뒤집는다.

 

예 제 : reverse

#include <iostream>

#include <algorithm>

using namespace std;

 

void main()

{

     int ari[]={1,2,3,4,5,6,7,8,9};

     int i;

 

     for (i=0;i<9;i++) printf("%d ",ari[i]);puts("");

     reverse(&ari[2],&ari[6]);

     for (i=0;i<9;i++) printf("%d ",ari[i]);puts("");

}

 

2번째 요소 ~ 5번째 요소까지의 순서가 반대로 뒤집어진다. 즉 ari[2]는 ari[5]와 교환되고 ari[3]은 ari[4]와 교환된다.

 

1 2 3 4 5 6 7 8 9

1 2 6 5 4 3 7 8 9

 

이 함수가 내부에서 어떤 처리를 할 것인가는 어렵지 않게 추측할 수 있으며 직접 만든다 하더라도 그다지 오랜 시간이 걸리지는 않을 것이다. 만들어 쓰는 것이 어려워서가 아니라 매번 만들기는 귀찮은 작업이라고 할 수 있다. 다음 함수는 컨테이너의 구간내 요소를 무작위로 마구 섞는다.

 

void random_shuffle(RanIt first, RanIt last);

 

게임을 만들 때 이 함수가 자주 사용되는데 퍼즐이나 카드패를 사용자가 예측하지 못하도록 할 때 무작위 섞기 기능이 사용된다. 예제를 보자.

 

예 제 : shuffle

#include <iostream>

#include <vector>

#include <algorithm>

#include <time.h>

using namespace std;

 

void main()

{

     int i;

     vector<int> vi(20);

     vector<int>::iterator it;

    

     for (i=0;i<20;i++) vi[i]=i;

     srand(time(NULL));

     random_shuffle(vi.begin(),vi.end());

     for (it=vi.begin();it!=vi.end();it++) {

          cout << *it << ' ';

     }

     cout << endl;

}

 

벡터에 0~19까지의 정수를 차례대로 집어 넣고 random_shuffle 함수로 섞었다. 이 함수가 내부적으로 난수를 사용하므로 난수 발생기는 먼저 초기화해 놓아야 한다. 매 실행할 때마다 섞이는 결과는 달라진다.

 

6 9 15 12 16 2 11 1 8 5 3 13 14 4 7 0 19 10 18 17

 

단 하나의 함수 호출로 패를 완전히 섞을 수 있다. STL에는 이 외에도 엄청나게 많은 알고리즘 함수들이 제공되는데 대략 60여개 정도 되며 앞으로 점점 더 늘어날 것이다. 각 함수별 사용예는 천천히 연구해 보도록 하고 일단 도표로 간단하게 목록만 정리해 보자. 양이 많아질 때는 대충 눈에만 익혀 두고 필요할 때 레퍼런스를 참조하는 것이 훨씬 더 현명한 처사다.

 

함수

설명

count

조건에 맞는 요소의 개수를 센다.

for_each

각 요소에 대해 지정한 작업을 한다.

equal

구간이 일치하는지 비교한다.

search

일치하는 부분 구간을 검색한다.

copy

구간끼리 복사한다.

fill

일정한 값으로 지정 구간을 채운다.

reverse

구간의 요소들을 반대로 뒤집는다.

random_shuffle

요소들을 무작위로 섞는다.

swap

컨테이너를 교환한다.

binary_search

이분 검색한다.

merge

구간을 병합하여 새로운 구간으로 복사한다.

accumulate

구간의 값을 모두 합한다.

 

왠만큼 직관력이 있는 사람은 함수 이름으로부터 기능을 대충 유추할 수 있을 것이다. copy는 복사하는 것이요 fill은 채우는 것이고 swap은 교환하는 것이고 merge는 병합하는 것이다. 필요할 때마다 이런 알고리즘을 일일이 만드는 것보다는 표준 알고리즘의 사용 방법을 대충이라도 알아 두는 것이 시간 절약과 체력 보존에 유리하다.