[C++] Algorithm 정리

Algorithm

#include <algorithm>

count

count(begin, end, value)

[begin, end)에 포함되어 있는 원소 중에서 value의 개수를 찾는다

count_if(begin, end, p)

[begin, end)에 포함되어 있는 원소 중에서 조건 p에 해당하는 것의 개수를 찾음

# 시간복잡도 : O(N)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    vector<int> a = {1, 4, 1, 2, 4, 2, 4, 2, 3, 4, 4};
    
    cout << "1의 개수 : " << count(a.begin(),a.end(),1) << endl;
    
    int even = count_if(a.begin(),a.end(),[](int x){
        return x%2 == 0;
    });
    
    int odd = count_if(a.begin(),a.end(),[](int x){
        return x%2 == 1;
    });
    
    cout << "짝수의 개수 : " << even << endl;
    cout << "홀수의 개수 : " << odd << endl;
}

📝10807번 문제 (개수 세기)

📝10808번 문제 (알파벳 개수)

Find

find(begin, end, value)

[begin, end)에 포함되어 있는 원소 중에서 value의 iterator

find_if(begin, end, p)

[begin, end)에 포함되어 있는 원소 중에서 조건 p에 해당하는 것의 iterator

# 두 함수 모두 못찾으면 end를 return

# 시간복잡도 : O(N)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    vector<int> a = {1, 4, 1, 2, 4, 2, 4, 2, 3, 4, 4};
    
    for(int i=1; i<=5; i++){
        auto it = find(a.begin(),a.end(),i);
        cout << i << "의 위치 : ";
        if(it == a.end())
            cout << "X" << endl;
        else
            cout << (it-a.begin()) << endl;
    }
    
    auto even = find_if(a.begin(),a.end(),[](int x){
        return x%2 == 0;
    });
    
    auto odd = find_if(a.begin(),a.end(),[](int x){
        return x%2 == 1;
    });
    
    cout << "첫번 째 짝수 : " << (even-a.begin()) << endl;
    cout << "첫번 째 홀수 : " << (odd-a.begin()) << endl;
}

📝10809번 문제 (알파벳 찾기)

Fill

fill(begin, end, value)

[begin, end)을 value로 채운다

# 시간복잡도 : O(N)

📝10810번 문제 (공 넣기)

Reverse

reverse(begin, end)

[begin, end)의 순서를 역순으로 만든다

# 시간복잡도 : O(N)

📝10811번 문제 (바구니 뒤집기)

Rotate

rotate(begin, mid, end)

[begin, end)을 mid 기준으로 왼쪽으로 회전시킨다

🔥역방향 반복자 (Reverse Iterator)

- 역방향 반복자는 ++, -- 시에 정방향 반복자와 반대로 동작한다

- v.begin() 은 v.rend() 와 같고, v.end() 은 v.rbegin() 과 같다

# 시간복잡도 : O(N)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void print(vector<int> &a){
    for(int x : a){
        cout << x << ' ';
    }
    cout <<endl;
}
 
int main(int argc, const char * argv[]) {
    vector<int> a = {0, 1, 2, 3, 4, 5};
    
    // 정방향 반복자 (Forward Iterator)
    for(int i=0; i<a.size(); i++){
        rotate(a.begin(), a.begin()+1, a.end());
        print(a);
    }
            /*
            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
            */
 
    // 역방향 반복자 (Reverse Iterator)
    for(int i=0; i<a.size(); i++){
        rotate(a.rbegin(), a.rbegin()+1, a.rend());
        print(a);
    }
            /*
             5 0 1 2 3 4
             4 5 0 1 2 3
             3 4 5 0 1 2
             2 3 4 5 0 1
             1 2 3 4 5 0
             0 1 2 3 4 5
             */
}

📝10812번 문제 (바구니 순서 바꾸기)

Swap

swap(a, b)

a와 b에 들어있던 값을 바꾼다

📝10813번 문제 (공 바꾸기)

Unique

unique(begin, end)

[begin, end) 구간에서 연속되는 값을 하나를 제외하고 제거

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

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

# 중복을 제거한 후의 End Iterator를 리턴한다

# 연속적인 값에서 중복을 제거

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    vector<int> a = {1, 1, 2, 2, 2, 3, 1, 1, 1, 2, 2, 2, 2};
    
    auto last = unique(a.begin(),a.end());
    
    // 원래 Vector인 a벡터는 변경X
    for(auto it=a.begin(); it!=last; ++it){
        cout << *it << ' ';     // 1 2 3 1 2
    }
    cout << endl;
    
    // 원래 Vector인 a벡터를 변경함
    // 만약 완전히 중복을 제거하고 싶다면
    // a.sort()후에 erase를 한다!
    a.erase(last,a.end());
    for(int x : a){
        cout << x << ' ';       // 1 2 3 1 2
    }
    cout << endl;
}

Sort

sort(begin, end)

[begin, end)를 <를 기준으로 정렬한다

sort(begin, end, cmp)

[begin, end)를 cmp 기준으로 정렬한다

🔥sort() 는 퀵정렬로 평균 n log(n) 의 시간복잡도를 가진다!

🔥cmp의 경우 const와 &를 붙여줘야 한다!!

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void print(vector<int> &a){
    for(int x : a){
        cout << x << ' ';
    }
    cout << endl;
}
 
// cmp
// const 와 & 를 붙여줘야함!!
bool cmp(const int &a, const int &b){
    return a > b;
}
 
int main(int argc, const char * argv[]) {
    vector<int> a = {5, 3, 2, 1, 4};
    
    // 역순 정렬하기
    sort(a.begin(), a.end(), greater<int>());
    print(a);   // 5 4 3 2 1
    
    // 큰 값부터 리턴
    sort(a.begin(), a.end(), [](int u,int v){
        return u > v;
    });
    print(a);   // 5 4 3 2 1
}

📝2750번 문제 (수 정렬하기)

📝1181번 문제 (단어 정렬)

📝11650번 문제 (좌표 정렬하기)

📝11651번 문제 (좌표 정렬하기2)

📝10825번 문제 (국영수)

🔥왜 다 시간초과가 뜨는건가!! ㅠㅠ

Stable Sort

stable_sort(begin, end)

[begin, end) 를 <를 기준으로 정렬한다

stable_sort(begin, end, cmp)

[begin,end) 를 cmp를 기준으로 정렬한다

# [ 7 5 2 5 ] 를 정렬했을때, [ 2 5 5 7 ] 또는 [ 2 5 5 7 ] 이런 식으로 정렬이 될 수 있다

# Stable Sorting은 같은 것이 있는 경우 정렬하기 전의 순서가 유지되는 정렬 알고리즘이다

📝10814번 문제 (나이순 정렬)

Binary Search

binary_search(begin, end, value)

[begin, end) 에서 value를 찾으면 true, 못 찾으면 false

binary_search(begin, end, value, cmp)

[begin, end) 에서 value를 cmp를 기준으로 찾으면 true, 못 찾으면 false

📝10815번 문제 (숫자 외우기)

Lower_bound / Upper_bound

lower_bound / upper_bound(begin, end, value, [cmp])

[begin, end) 에서 value보다 (작지 않은 / 큰) 첫 번째 Iterator

📝10815번 문제 (숫자 카드2)

Min / Max

min/max(a, b)

min/max(a, b, cmp)

min/max(initializer_list)

min/max(initializer_list, cmp)

# minmax

# min과 max를 동시에 구할 수 있다

minmax(a, b)

minmax(a, b, cmp)

minmax(initializer_list)

minmax(initializer_list, cmp)

📝10817번 문제 (세 수)

Min_element / Max_element

min_element/max_element(begin, end)

[begin, end)에서 최소/최대값의 Iterator를 구한다

min_element/max_element(begin, end, cmp)

[begin, end)에서 cmp를 기준으로 최소/최대값의 Iterator를 구한다

# minmax_element

# min과 max의 Iterator를 동시에 구한다

minmax_element(begin, end)

minmax_element(begin, end, cmp)

auto minmaxValue = minmax(v.begin(), v.end());

minmaxValue.first

minmaxValue.second

📝10818번 문제 (최소, 최대)

🔥타입확인하기

- #include <typeinfo>

- typeid(target).name() 으로 확인

Next_permutation

next_permutation(begin, end)

next_permutation(begin, end, cmp)

prev_permutation(begin, end)

prev_permutation(begin, end, cmp)

[begin, end)를 순열이라고 생각했을때, 사전 순으로 다음에 오는 순열을 만든다

마지막 순열이면 false를 리턴

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(int argc, const char * argv[]) {
    vector<int> v = {3,1,2};
    
    sort(v.begin(), v.end());
    
    do{
        for(int x : v){
            cout << x << ' ';
        }
        cout << endl;
    }while(next_permutation(v.begin(), v.end()));
}

📝10819번 문제 (차이를 최대로)

🔥절대값 구하기

- #include <cmath>

- abs() 를 사용하여 절대값을 구함

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main(){

    vector<int> v = {-1, 2, -10};

    

    for(int x : v) {

        cout << abs(x) << ' ';

    }

    cout << endl;

    // 1 2 10

}