백준 정렬 모음집 - 1

각 파트별로 좀 여러 문제를 많이 풀 필요성을 느낌! 

 

 

백준 1427번 - Silver V

#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
    string str;
    cin>>str;
    sort(str.begin(),str.end(),greater<char>());//내림차순
    cout <<str;
}

 

백준 11650번 - Silver V

 

- 2 차원 벡터 초기화 방법

vector<vector<int>> v(3, vector<int>(5,0); //3행 5열을 0으로 초기화

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
    int n;
    cin>>n;
    vector<vector<int>> vc(n,vector<int>(2,0)); //n행 2열 0으로 초기화
    for(int i=0;i<n;i++){ // 순서대로 입력
        cin>>vc[i][0];
        cin>>vc[i][1];
    }
    sort(vc.begin(), vc.end());// 오름차순 정렬
    for(int i=0;i<vc.size();i++){
        cout <<vc[i][0]<<" "<<vc[i][1]<<"\n"; //endl로 하면 시간 초과!
    }
}

 

백준 11651번 - Silver V

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
    vector<pair<int, int>> v;
    int n, a, b;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        v.push_back(pair<int, int>(b, a));
        
    }
    sort(v.begin(), v.end()); //y좌표 기준으로 정렬
    for (int i = 0; i < n; i++){
        cout << v[i].second <<" " << v[i].first<<"\n";
        
    }
    
}

 

백준 1181번 - Silver V

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool lcomp(string a, string b){
    if(a.length()==b.length()){
        for(int i=0;i<a.length();i++){
            if(a[i]!=b[i]){
                return a[i]<b[i];
            }
        }
    }
    return a.length()<b.length();
}
int main(void) {
    int n;
    string str;
    cin>>n;
    vector<string>vc;
    for(int i=0;i<n;i++){
        cin>> str;
        vc.push_back(str);
    }
    sort(vc.begin(),vc.end(),lcomp);
    //cout <<vc[0]<<"sdfsd\n";
    
    for(int i=0;i<n;i++){
        if(vc[i]==vc[i+1]){ // 중복 넘어가기
            continue;
        }
        cout <<vc[i]<<"\n";
    }
}

 

백준 10814번 - Silver V

•  stable_sort

: 정렬을 했을 때 중복된 값들의 순서가 변하지 않으면 안정(Stable) 정렬, 변하면 불안정(Unstable) 정렬

 

Stable Sorting 알고리즘:

• Insertion Sort
• Merge Sort
• Bubble Sort
• Counting Sort

Unstable Soring 알고리즘:

• Selection sort
• Heap Sort
• Shell Sort
• Quick Sort

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool compare(pair<int,string>a, pair<int,string>b){
    return a.first < b.first;
}
int main(void) {
    int n;
    cin>>n;
    pair<int,string>str;
    vector<pair<int,string>>vc;
    for(int i=0;i<n;i++){
        cin>>str.first>>str.second;
        vc.push_back(str);
    }
    stable_sort(vc.begin(),vc.end(),compare); //stable_sort 정렬 사용
    
    for(int i=0;i<n;i++){
        cout <<vc[i].first<<" "<<vc[i].second<<"\n";
    }
}

 

 

백준 2752번 - Bronze IV (선택정렬)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(void) {
    int arr[3];
    for(int i=0;i<3;i++){
        cin>>arr[i];
    }
    for(int i=0;i<2;i++){
        for(int j=i+1;j<3;j++){
            if(arr[j]<arr[i]){
                int tmp=arr[i];
                arr[i]=arr[j];
                arr[j]=tmp;
            }
        }
    }
    for(int i=0;i<3;i++){
        cout << arr[i]<<" ";
    }
    cout <<"\n";
    return 0;
}

 

 

 

---

 

참고

https://velog.io/@cookncoding/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-Stable-Sort-Inplace

[알고리즘 개념] Stable Sort &Inplace