Jisang Yoo 님이 쓰신 글 :
: int IntArr[100];
: for(int i=0 ; i<100 ; i++)
: IntArr[i] = 2*i;
: int Val = 55;
:
: 위에서처럼 int의 배열인 IntArr가 있고, 배열 IntVarr 은 크기가 작은 수부터 큰 수의 순서로 소트되어있는 상태라고 합시다.
: 그리고 또다른 int 변수인 Val 이 있는데, 하고 싶은 것은,
: IntArr 배열 안에 있는 수들 중에서 Val 보다 작은 수들 중 가장 큰 수의 인덱스를 찾는 것입니다.
: 즉, IntArr 안에 있는 수들 중에서 Val보다 작은 것들 중 Val 과 가장 가까운 수를 찾는 것인데,
: 이런 일을 하는 STL 함수가 있나요?
"STL 함수"라는 용어보다는 보통 "STL 알고리듬(algorithm, '알고리즘'은 th를 일본식 발음으로 '즈'로 하는데서 유래합니다.)"이라는 용어를 씁니다. 인자로 [first, last)와 같은 반복자(iterator)의 범위를 갖는 (템플릿) 함수를 알고리듬이라고 합니다.
: 이런 일을 할 때, IntArr[0] ,IntArr[1], .... 이런 식으로 순서대로 차례차례로 비교하면 O( N) 의 시간이 걸리는데,
: IntArr가 이미 소트된 상태라는 것을 이용해서 O(logN) 의 시간이 걸리는 방법으로 이 일을 해주는 STL함수가 무엇인가요?
소트된 상태에서 O(log N)의 시간으로 검색하는 방법을 이진 검색(binary search)라고 합니다.
자료구조나 알고리듬 관련 책, 또는 좀 두꺼운 C 언어 책에서도 찾을 수 있는 내용이죠.
이진 검색은 ANSI C 라이브러리에도 bsearch()라는 함수가 있죠.
(순차 검색을 위한 lsearch()나 lfind()도 있습니다만, 굳이 쓸 필요가 없죠. -_-)
문제는, 반드시 함수 포인터를 사용해야 하기 때문에 성능이 상당히 좋지 않습니다.
(실행 파일 크기보다 속도를 우선해야 한다면, 함수 포인터 대신 함수 객체(function object)를 사용하세요.)
하여튼, qsort()와 함께 절대 비추하는 함수입니다!
대신, STL의 이진 검색 알고리듬을 쓰실 것을 권합니다.
(bsearch보다 몇 천에서 몇 만배 정도 빠릅니다. 절대 뻥 아닙니다. *^^*
왜 그런지는 Effective STL의 Item 46을 참고하세요.)
STL의 검색 알고리듬에 대해서는 제가 이전에 C/C++ Tip'N Tricks에 올린 글이 있습니다.
http://www.borlandforum.com/impboard/impboard.dll?action=read&db=cpp_tip&no=25
자세한 설명을 위해 만들어 본 코드입니다.
코드를 보시고 직접 실행해 보시면 필~~이 오실 겁니다.
//---------------------------------------------------------------------------
#include <iostream>
#pragma hdrstop
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iterator>
//---------------------------------------------------------------------------
using namespace std;
#pragma argsused
int main(int argc, char* argv[])
{
// int IntArr[100];
// for(int i = 0; i < 100 ; i++)
// IntArr[i] = 2 * i;
// 위의 루프를 사용한 코드 대신 STL 알고리듬을 사용한 코드입니다.
vector<int> IntVec(100);
// iota는
http://www.borlandforum.com/impboard/impboard.dll?action=read&db=cpp_tip&no=5 F를 참고하세요.
iota(IntVec.begin(), IntVec.end(), 0);
transform(IntVec.begin(), IntVec.end(), // source
IntVec.begin(), // destination
bind2nd(multiplies<int>(), 2)); // operation (i * 2)
// 또는 다음과 같이 해도 동일한 결과가 됩니다(속도는 약간 더 느립니다.).
// transform(IntVec.begin(), IntVec.end(), // first source
// IntVec.begin(), // second source
// IntVec.begin(), // destination
// plus<int>()); // operation (i + i)
// IntVec 의 내용을 출력하려면 다음과 같이 합니다.
copy(IntVec.begin(), IntVec.end(), ostream_iterator<int>(cout, " "));
cout << endl;
const int Val = 55;
// IntVec 안에 있는 값들 중에서 Val 보다 작은 값들 중
// 가장 큰 값의 인덱스를 찾으려면, lower_bound 알고리듬을 사용합니다.
// lower_bound는 원하는 값을 "삽입할" 첫번째 위치를 찾습니다.
vector<int>::iterator vp = lower_bound(IntVec.begin(), IntVec.end(), Val);
// 일단 IntVec 안의 모든 값이 Val 보다 작은 지를 알아보려면,
if (vp == IntVec.end())
cout << "IntVec 안의 모든 값이 Val 보다 작습니다.\n";
else if (*vp == Val) // Val과 동일한 값인지도 체크해야 합니다.
cout << "IntVec의 " << vp - IntVec.begin() // 배열에서의 포인터 연산과 유사합니다.
<< "번째 위치에 Val과 동일한 값이 있습니다.\n";
else // (0부터 센다고 할 때) "삽입할" 위치에서 1을 빼면 원하는 위치가 됩니다.
cout << "IntVec의 " << vp - IntVec.begin() - 1
<< "번째 위치에 Val보다 작은 값들 중 가장 큰 값이 있습니다.\n";
return 0;
}
//---------------------------------------------------------------------------
