algorithm 라이브러리 줍줍

코딩테스트 대비

코테를 준비면서 공부를 하다 보면 algorithm 라이브러리를 만날 수 있다. 보다보면 편리한 내장함수들이 상당히 많이 있는데 이걸 다 외우는 건 힘들거 같고,,,, 제일 쓸만한거만 정리할 수 없나...? 해서 제가 해봄...ㅎㅎ...

저는 실력이 뛰어나지 않으므로 제 기준을 믿지 마시고 그래도 아 이런거는 잘 쓰이는구나.. 정도로 생각해주시면 될 것 같슴돻ㅎ,,,,,,,

sort

순차열에 대해 사용이 가능하며 반복자와 정렬 기준을 인자로 받는다.

sort(v.begin(), v.end(), function) 

정렬할 위치의 시작점, 끝점을 입력해주고 정렬 기준이 되는 function을 넣어주면 되는데 여기서 function은 두 인자를 받아 비교 연산을 수행한 후 bool type을 return 해야한다.

일단 기본적인 사용법은 아래 코드를 통해 확인할 수 있다. 랜덤하게 9이하의 정수를 벡터에 삽입해주었고, 이를 정렬한 결과를 보여주는 형태이다.

// sort 사용법

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> jaewon;

int main() {
    vector<int>::iterator iter;

    for(int i=0;i<10;i++){
        jaewon.push_back(rand() % 10);
    }

    for(iter = jaewon.begin() ; iter != jaewon.end() ; iter ++){
        cout << *iter << " "; 
    }
    cout << endl;

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

    for(iter = jaewon.begin() ; iter != jaewon.end() ; iter ++){
        cout << *iter << " "; 
    }

    return 0;
}

❯ 
7 9 3 8 0 2 4 8 3 9 
0 2 3 3 4 7 8 8 9 9 %  

sort는 기본적으로 오름차순 정렬(작 -> 큰)을 수행하는데 내림차순 정렬을 위해서는 위에서 언급한 비교연산 함수가 필요하다. 이를 Greater로 정의하고 사용해보면 아래와 같다.(처음에 greater로 했는데 안되서 g->G 로 하니까 되는데 아마 greater이 뭔가 있는둣...?ㅋㅋㅋ)

bool Greater(int a, int b){
    return a > b;
}

...

sort(jaewon.begin(), jaewon.end(), Greater);

❯ 
7 9 3 8 0 2 4 8 3 9 
9 9 8 8 7 4 3 3 2 0

정상적으로 내림차순 정렬을 확인할 수 있다. sort는 단순히 정수 비교 뿐만 아니라 내가 선언한 data type에 대해서도 정렬이 가능하고 이 때는 비교연산 함수가 정렬 기준이 되므로 함수의 올바른 작성이 중요하!!

lower_bound

lower_bound() 또는 upper_bound() 알고리즘은 순차열에서 같은 원소를 찾기 위한 방법이다. 예를 들어

p = lower_bound(v.begin(), v.end(), jaewon);
p = upper_bound(v.begin(), v.end(), jaewon);

는 v(vector)의 처음부터 끝까지의 범위 내에서 jaewon과 같은 값을 갖는 첫번째 원소(lower_bound의 경우) 또는 마지막 원소의 다음 원소(upper_bound의 경우)를 반환해준다.

음,,, 이건 그렇게 많이 쓰이지는 않는데 같은 문자가 반복되는 형태에서 반복되는 문자열을 찾아낼 때..? 정도 사용한다고 생각하면 댑니다 ㅎㅎ,,,,

min, max

이름 그대로 parameter로 넘겨받은 인자를 비교해준다. 일반 <, > 연산과 달리 특이점은 위의 sort에서 사용한 것과 같이 비교연산 함수를 이용한 비교가 가능하다. 음,, 코드를 먼저 보는게 더 이해하기 편할 것 같당 ㅋ

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class student {
    int age;
    int height;
    int stID;
    public : 
        student(int _age = 0, int _height = 0, int _stID = 0) : age(_age), height(_height), stID(_stID){}
        int getAge() const { return age; }
        int getHeight() const { return height; }
        void hello() const { cout << "hello I'm " << getAge() << " " << getHeight() << endl; }
};


bool AgeCompare(student s1, student s2){
    return s1.getAge() < s2.getAge();
}

bool HeightCompare(student s1, student s2) {
    return s1.getHeight() < s2.getHeight();
}

int main() {
    student jaewon(32, 178, 00000000);
    student heeju(29, 168, 00000001);

    student s1 = max(jaewon, heeju, AgeCompare);
    student s2 = min(jaewon, heeju, HeightCompare);

    s1.hello();
    s2.hello();

    return 0;
}

음,, 그냥 min, max를 다른 자료형에 사용하는 예제를 만들어보려고 class를 선언하고 각 class의 멤버변수들을 비교해줄 수 있는 비교함수를 작성하였다. (AgeCompare, HeightCompare) 이 두가지 함수를 이용해서 jaewon과 heeju의 키, 나이를 비교하였고, 위 코드를 통해 출력되는 결과는 아래와 같다.

❯ 
hello I'm 32 178
hello I'm 29 168

나이가 많은 사람을 골라라 해서 jaewon이 선택되었고, 키가 작은 사람을 골라라 해서 heeju가 선택됨을 알 수 있다.

공부를 더 하면서 추가하고 싶은 것들이 생기면 이 글에 더 추가하겠당 ㅎ