#INFO 난이도 : SILVER5 문제유형 : 정렬 알고리즘 출처 : https://www.acmicpc.net/problem/2751 #SOLVE 제한시간이 2초이고, N이 최대 1,000,000 이기에 버블정렬 같은 O(N^) 이상의 시간복잡도가 걸리는 정렬 알고리즘을 사용하면 시간초과가 발생한다. 따라서 Intro Sort로 구현된 시간복잡도 O(Nlogn)을 가지는 C++ STL에서 제공하는 sort 함수를 사용했다. _About Sort Function #CODE #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int arr[1000..

#INFO 난이도 : SILVER5 문제 유형 : 정렬 출처 : 10814번: 나이순 정렬 (acmicpc.net) #SOLVE 문제에서 주어진 정렬 조건은 다음과 같다. 1. 회원들의 나이가 증가하는 순으로 정렬한다. 2. 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬한다. 2번 조건이 없었다면 pair 만으로 해결할 수 있었겠지만, 먼저 가입한 사람의 순서를 파악하기 위해서 C++ STL의 tuple과, sort 정렬함수를 사용했다. vector info; // 1st int : 나이 // 2nd string : 이름 // 3rd int : 가입 순서 tuple은 pair의 확장 버전이라고 생각하면 되는데, 3개 이상의 자료형을 하나로 묶어 사용할 수 있다. 따라서 tuple의 세번째 자료..

#INFO 난이도 : SILVER5 문제 유형 : 정렬 출처 : 11651번: 좌표 정렬하기 2 (acmicpc.net) #SOLVE BOJ 11650 좌표 정렬하기 문제랑 거의 같은 문제이다. sort 함수 내부에서 pair는 first(x좌표)를 기준으로 오름차 정렬 되기 때문에 3번째 인자로 second(y좌표)를 기준으로 오름차 정렬하고, second(y좌표)가 같을 경우 first(x좌표)를 기준으로 오름차 정렬하는 bool형 compare 함수를 정의해 주면 된다. #CODE #include using namespace std; bool compare(const pair& p1, const pair& p2){ if(p1.second == p2.second) // y좌표가 같으면 return p..

#INFO 난이도 : SILVER5 문제 유형 : 정렬 출처 : 11650번: 좌표 정렬하기 (acmicpc.net) #SOLVE 시간복잡도를 생각하지 않고 무작정 구현했더니, 시간초과가 발생했다. 아래는 모든 원소를 차례로 비교하는 방식의 알고리즘인데, 이는 n의 값이 100,000이 되었을 때 거의 100초에 달하는 시간이 걸리게된다. #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector xy; xy.resize(n); for(int i = 0; i > xy[i].first >> xy[i].second;..

INFO C++ STL 라이브러리의 algorithm 헤더는 sort 정렬 함수를 제공합니다. sort 정렬 함수는 intro sort 정렬 알고리즘을 이용하는데 이는 quick sort 정렬 알고리즘을 기반으로 한 heap sort 와 insertion sort 를 혼합해 만든 알고리즘으로 최악의 경우에 n^2의 시간 복잡도를 가지는 quick sort의 단점을 보완하여 최악의 경우에도 nlogn의 시간 복잡도를 가지는 정렬 알고리즘 입니다. PS에서 빈번하게 사용되는 함수이기에, 한 번 숙지해 두면 알고리즘 풀이에 큰 도움이 될 것 입니다. #1 오름차순 정렬 - 1.1 벡터 오름차순 정렬 예제 - 1.2 배열 오름차순 정렬 예제 #2 내림차순 정렬 - 2.1 벡터 내림차순 정렬 예제 - 2.2 배열..