2. pair, sort, binary search

SCCC - Soongsil Computing Contest Club/2020 Winter-Study

2. pair, sort, binary search

Mosu(정종인) 2020. 1. 8. 02:51

복습
boj.kr/1001
pair


#include <iostream>
using namespace std;

int main(){
    pair<int, int> mypair;
    cin >> mypair.first >> mypair.second;

    cout << mypair.first << ' ' << mypair.second; << '\n';

    if(mypair == make_pair(3, 4)) {}
    if(mypair < make_pair(4, 5)) {}
}

두 가지 변수를 묶고싶을 때 구조체 대신 이걸 쓰면 편리하다.

참고 문제 : [ boj.kr/11650, boj.kr/11651 ]

sort 심화

sort의 세번째 인자로 비교방식을 커스텀할 수 있음.


sort(arr, arr + N, [](const int & a, const int& b) {return a<b; });


auto cmp = [](pair<int, int> a, pair<int, int> b) {
  if(a.first == b.first) return a.second < b.second;
  return a.first < b.first;
} // 변수

bool cmp(pair<int, int> a, pair<int, int> b) {
  if(a.first == b.first) return a.second < b.second;
  return a.first < b.first;
} // 함수

sort(arr, arr + N, cmp);

auto : 컴파일 할때 알아서 타입을 결정해주는 키워드.

람다식 : 코드 중간에 간단한 함수를 바로 만들어서 삽입하는 것이라고 생각하면 됨. c++14부터 지원.


struct AA {
  int a;
  int b;
  string str;
  vector<int> arr;
  pair<int, int> p;

  bool operator<(AA a, AA b) { //연산자 오버로딩
    return a.a < b.a; // a끼리만 비교하려면 이렇게
  }
}

int main(){
  AA arr[100], b;
  sort(arr, arr+100); // 연산자 오버로딩으로 정렬이 가능.
}

참고 : stable sort는 중복된 값들의 순서를 유지, unstable sort는 순서를 보장하지 못함.

c++의 sort는 unstable sort임.

참고 문제 : [boj.kr/10814, boj.kr/11931, boj.kr/15819, boj.kr/11656]

lower bound, upper bound, binary search

[1, 3, 4, 5, 6, 100, 6000, 7000, 10000] 의 정렬된 배열에서 이 배열 안에 어떤 값이 존재하는지, 어디에 존재하는지 알고 싶다.

binary_search(), lower_bound(), upper_bound()를 적절히 사용해보자. 헤더파일 algorithm 포함 필수.


#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;

int main(){
  srand(time(NULL));
  int arr[10];
  for(int i=0; i<10; ++i){
    arr[i]=rand();
  }
  for(int i=0; i<10; ++i){
    cout << arr[i] << " \n"[i==9]; // 랜덤으로 값 넣어주기
  }

  //1. binary search
  while(true) {
    int val;     cin >> val;
    cout << (binary_search(arr, arr + 10, val) ? "True":"False") << '\n'; // 리턴값이 0 또는 1
  }

  //2. lower bound * 중요 , upper bound
  while(true) {
    int val;     cin >> val;
    int * pos = lower_bound(arr, arr+10, val); // 정렬된 배열에서 lower bound를 리턴함.
    int * pos2 = upper_bound(arr, arr+10, val); // 정렬된 배열에서 upper bound를 리턴함
    cout << (pos-arr) << ' ' << (pos2-arr) << '\n'; // 리턴값이 포인터라서 이렇게 해야 위치가 나옴
    /*
    2 3 4 5 6 8 9가 있을 때 lower_bound의 val에 4를 넣으면 pos-arr = 3,
    lower 대신 upper_bound를 하면 pos-arr = 4

    2 3 4 4 4 5 6 7 8 9가 있을 때 lower_bound, uppder_bound에 4를 넣고 돌리면
    각각 2, 5를 반환하고, 즉 4가 [2, 5) 의 구간에 있다고 생각할 수 있다.

    */
  }
}

참고 문제 : [boj.kr/2467 = boj.kr/2470, boj.kr/2230, boj.kr/1920, boj.kr/7453]

부록 : 참고 문제 풀이

boj.kr/11650


#include <iostream>
#include <algorithm>
using namespace std;

pair<int, int> arr[100001];

int main(){
    int N;
    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i].first >> arr[i].second;
    }
    sort(arr, arr+N);
    for(int i=0; i<N; ++i){
        cout << arr[i].first << ' ' << arr[i].second << '\n';
    }
}

boj.kr/11651


#include <iostream>
#include <algorithm>
using namespace std;
pair<int,int> arr[100001];

bool cmp(pair<int, int> a, pair<int, int> b) {
  if(a.second == b.second) return a.first < b.first;
  return a.second < b.second;
}

int main(){
    int N;
    cin >> N;

    for(int i=0; i<N; ++i){
        cin >> arr[i].first >> arr[i].second;
    }
    sort(arr, arr+N, cmp);
    for(int i=0; i<N; ++i){
        cout << arr[i].first << ' ' << arr[i].second << '\n';
    }
}

boj.kr/10814


#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct mem {
    int age;
    string name;
    int create;
};
bool cmp(const mem a, const mem b) {
    if(a.age == b.age) return a.create < b.create;
    return a.age < b.age;
}
mem arr[100001];
int main(){
    int N;
    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i].age >> arr[i].name;
        arr[i].create = i;
    }
    sort(arr, arr+N, cmp);
    for(int i=0; i<N; ++i){
        cout << arr[i].age << ' ' << arr[i].name << '\n';
    }

}

boj.kr/11931


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v;
bool cmp(const int a, const int b){
    return a>b;
}
int main(){
    int N;
    cin >> N;
    for(int i=0; i<N; ++i){ 
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end(), cmp);
    for(int i=0; i<N; ++i){
        cout << v[i] << '\n';
    }
}

boj.kr/15819


#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string arr[1000];
int main(){
    int N, l;
    cin >> N >> l;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }
    sort(arr, arr+N);
    cout << arr[l-1] << '\n';
}

boj.kr/11656


#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
vector<string> v;

int main(){
    string s;
    cin >> s;

    for(int i=s.size()-1; i>=0; --i) {
        v.push_back(s.substr(i));
    }
    sort(v.begin(), v.end());
    for(int i=0; i<s.size(); ++i){
        cout << v[i] << '\n';
    }
    return 0;
}

boj.kr/2467 = boj.kr/2470


#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long int ll;



pair<ll, pair<ll, ll> > p;
ll arr[100001];
int main(){
    int N;
    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }
    sort(arr, arr+N);
    p.second.first = arr[0];
    p.second.second = arr[N-1];
    p.first = p.second.first + p.second.second;
    int f = 0, l = N-1;
    while (f<l) {
        if(abs(arr[f]+arr[l]) < abs(p.first)) {
            p.first = arr[f]+arr[l];
            p.second.first = arr[f];
            p.second.second = arr[l];
        }
        if(abs(arr[f]) < abs(arr[l])){
            l-=1;
        }
        else f+=1;
    }
    cout << p.second.first << ' ' << p.second.second << '\n';

}

boj.kr/2230


#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;
ll arr[100001];

int main(){
    ll N;
    ll M;
    cin >> N >> M;

    for(ll i=0; i<N; i+=1){
        cin >> arr[i];
    }
    sort(arr, arr+N);

    ll res=20000000001;

    for(ll i=0; i<N; i+=1){
        ll *pt=lower_bound(arr, arr+N, arr[i]+M);
        ll k = pt-arr;
        if(k>=N) continue;
        if(arr[k]-arr[i]<res) res = arr[k]-arr[i];
    }
    cout << res << '\n';
}

boj.kr/1920


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int arr[100001], t;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N, M;
    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
    }
    sort(arr, arr+N);
    cin >> M;
    for(int i=0; i<M; ++i){
        cin >> t;
        if(binary_search(arr, arr+N, t)) cout << '1' << '\n';
        else cout << '0' << '\n';
    }
}

boj.kr/7453


#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;

vector<ll> A_B, A, B, C, D;
int main(){
    int N;
    cin >> N;
    for(int i=0; i<N; ++i){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        A.push_back(a);
        B.push_back(b);
        C.push_back(c);
        D.push_back(d);
    }
    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            A_B.push_back(A[i]+B[j]);
    ll cnt=0, k=0;
    sort(A_B.begin(), A_B.end());
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            k=(upper_bound(A_B.begin(), A_B.end(), -(C[i]+D[j])) - lower_bound(A_B.begin(), A_B.end(), -(C[i]+D[j])));
            if(k) cnt+=k;
        }
    }
    cout << cnt << '\n';
}

저작자표시 (새창열림)