[C++] <algorithm> 라이브러리 속 유용한 함수

1) <algorithm>

• #include <algorithm>
• 원소들에 대해 작업할 수 있는 여러가지 함수들을 정의하고 있는 라이브러리.

 

 

2) 주요 함수

• count(begin, end, value) : [begin, end] 에 포함되어 있는 원소 중에서 value의 개수를 찾는다.
• count_if (begin, end, p) : [begin, end] 에 포함되어 있는 원소 중에서 조건 p에 해당하는 value의 개수를 찾는다.

 

# begin, end = iterator

# p = 함수 pointer

# 시간복잡도 : O(N)

 

bool is_big(int x) {
	return (x > 2);
}

int main() {
	vector<int> v = {1, 4, 1, 2, 4, 2, 4, 2, 4, 3, 4, 4};
    
    for(int i = 1; i <= 5; i++) {
    	cout << i << ": " << count(v.begin(), v.end(), i) << '\n';
        }
	cout << "bic : " << count_if(v.begin(), v.end(), is_big) << '\n';
    
    int even = count_if(v.begin(), v.end(), [](int x) {
    	return x % 2 == 0;
        });
   	cout << "even: " << even << '\n';
   
    int odd = count_if(v.begin(), v.end(), [](int x) {
    	return x % 2 == 1;
        });
     cout << "odd: " << odd << '\n';

 

• find (begin, end, value) : [begin, end] 에 포함되어 있는 원소 중에서 value의 iterator.
• find_if (begin, end, p) : [begin, end] 에 포함되어 있는 원소 중에서 조건 p에 해당하는 것의 iterator.

 

# 두 함수 모두 못찾으면 end()를 리턴.

# 시간복잡도 O(N)

 

예제1)

vector<int> v = {1,2,5,4,3,2,4,3,1,2,6};

for(int i = i; i <= 7; i++) {
	auto it = find(v.begin(), v.end(), i);
    cout << i << "s' position: ";
    
    if (it == v.end()) {
    	cout << "not found" << '\n';
    }
    else {
    	cout << (it-v.begin()) << '\n';
    }
}

예제2)

vector<int> v = {1, 2, 5, 4, 3, 2, 4, 3, 1, 2, 6};
    
vector<function<bool(int)>> op;
op.push_back([](int x) {
    return (x%2==0);
});
op.push_back([](int x) {
    return (x%3==0);
});
op.push_back([](int x) {
    return (x%5==0);
});
    
for(auto &f : op) {
    int res = find_if(v.begin(), v.end(), f) - v.begin();
    cout << res << '\n';
}

 

• fill(begin, end, value) : [begin, end)을 value로 채운다.

 

#시간복잡도 : O(N)

vector<int> a = {1, 4, 1, 2, 4, 2, 4, 2, 3, 4, 4};

for (int x : a) {
	cout << x << ' ';            // 1 4 1 2 4 2 4 2 3 4 4
    }
cout << '\n';

fill(a.begin(), a.end(), 0);
for(int x : a) {
	cout << x << ' ';            // 0 0 0 0 0 0 0 0 0 0 0 
}
cout << '\n';

 

• reverse(begin, end) : [begin, end)의 순서를 역순으로 만든다.

#시간복잡도 : O(N)

vector<int> a = {1,4,1,2,4,2,4,2,3,4,4};

for (int x : a) {
	cout << x << ' ';        // 1 4 1 2 4 2 4 2 3 4 4
}
cout << '\n';

reverse(a.begin(), a.end());

for(int x : a) {
	cout << x << ' ';        // 4 4 3 2 4 2 4 2 1 4 1
}
cout << '\n';

 

• rotate(begin, mid, end) : [begin, end)를 mid 기준으로 왼쪽으로 회전시킨다.

# 시간복잡도 : O(N)

 

vector<int> a = {0,1,2,3,4,5};
int n = a.size();

for(int i = 0; i < n; i++) {
	rotate(a.begin(), a.begin() + 1, a.end());
    
    for(int x : a) cout << x << ' ';
    cout << '\n';
}

result ) 

1 2 3 4 5 0

2 3 4 5 0 1

3 4 5 0 1 2

4 5 0 1 2 3

5 0 1 2 3 4

0 1 2 3 4 5

 

• swap(a,b) : a와 b에 들어있던 값을 바꾼다

int a = 10, b = 20;
cout << a << ',' << b << '\n';     // 10, 20

swap(a,b);
cout << a << ',' << b << '\n';     // 20, 10

vector<int> a = {1,2};
vector<int> b = {3,4};
cout << a[0] << ',' << b[0] << '\n';  // 1,3

swap(a,b);
cout << a[0] << ',' << b[0] << '\n';  // 3,1

 

• unique(begin, end) : [begin, end) 구간에서 연속되는 같은 값을 하나 제외하고 제거한다.

# 실제로 컨테이너의 크기를 줄이거나 제거하지는 않는다.

# 중복을 덮어씌우거나 시프트 시키는 방식으로 작동한다.

# 중복을 제거한 후에 end iterator를 반환한다.

    vector<int> a = {1,1,2,2,2,3,1,1,1,2,2,2,2};
    for(int x : a) cout << x << ' ';
    cout << '\n';
    
    auto last = unique(a.begin(), a.end());
    for(int x : a) cout << x <<  ' ';
    cout << '\n';
    
    cout << *last << '\n';
    for(auto it = a.begin(); it != last; ++it)
        cout << *it << ' ';
    cout << '\n';

 

• sort(begin, end) : [begin, end)를 오름차순 정렬한다.

# 2개의 요소 L,R이 있을 때 L < R이 true인 상황으로 정렬한다.

 

- sort(begin, end, cmp) : [begin, end)를 'cmp' 함수가 참(true) 인 형태로 정렬한다.

bool cmp(const int& L, const int& R) {
	return L > R;
}

int main() 
{
	vector<int> a = {5, 3, 2, 1, 4};
    
    for(int x : a) cout << x << ' ';           // 5 3 2 1 4
    cout << '\n';
    
    sort(a.begin(), a.end(), greater<int>());
    sort(a.begin(), a.end(), cmp);
    sort(a.begin(), a.end(), [](int L, int R) {
    	return L > R;
    });
    for (int x : a) cout << x << ' ';          // 5 4 3 2 1
    cout << '\n';
 }

 

• binary_search(begin, end, value) : [begin, end)에서 value를 찾으면 true, 못 찾으면 false.
• binary_search(begin, end, value, cmp) : [begin, end)에서 cmp를 기준으로 value를 찾으면 true, 없으면 false.

 

vector<int> a = {1, 5, 6, 7, 10, 20};
    
for(int i = 1; i <= 10; i++) {
    cout << i << ": ";
    cout << binary_search(a.begin(), a.end(), i) << endl;
}

 

• min/max (a, b) : a와 b중 최소값/최대값
• min/max (a, b, cmp) 
• min/max (initalize_list) : initialize_list 중 최소값 / 최대값
• min/max (initialize_list, cmp)

 

• minmax : min, max 값을 pair형태로 반환 (first 는 최소값, second 는 최대값)