pushback

2750번과 마찬가지로 sort함수를 이용하여 해결하였습니다.

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

int num[1000001];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> num[i];
    
	sort(num, num + n);

	for (int i = 0; i < n; i++) cout << num[i] << '\n';
    
	return 0;
}

sort함수를 이용하여 가볍게 풀이하였습니다. 

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

int num[1000];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> num[i];
	sort(num, num + n);

	for (int i = 0; i < n; i++) cout << num[i] << '\n';
	return 0;
}

sort함수는 세 개의 인자를 받습니다. sort(배열의 시작, 배열의 끝, 정렬 방법) 이라고 생각하시면 편합니다. 세번째 인자를 생략하면 자동 오름차순으로 정렬됩니다.

좀 더 정확히 설명해봅시다.

int arr[5] = { 4, 3, 2, 1, 0 };

int형 원소들을 갖고 있는 arr배열을 오름차순으로 정렬하고싶다면,

sort(arr, arr + 5); 

이 코드 한줄로 끝나게 됩니다.

한가지 의문이 듭니다. 왜 배열의 끝이 arr + 4가 아니라 arr + 5일까 ?

밑에 그림을 보겠습니다.

간단하쥬 ? 이 그림이 이해가 안가신다면 포인터 개념을 공부해주시면 됩니다.

이번엔 vector를 이용해봅시다.

vector<int> vec = { 4, 3, 2, 1, 0};

위에 배열과 같은 원소를 갖는 vector를 만들었습니다. 

마찬가지로 오름차순으로 정렬하고 싶습니다. 

sort(vec, vec + 5);

하면 에러입니다. 

vector는 STL에서 제공하는 자료구조이기 때문에 iterator(반복자)를 인자로 넣어주어야 합니다.

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

이 옳은 방법입니다.

혹시 vector에서 모든 원소 정렬이 아닌 원하는 부분만 정렬하고 싶다면,

sort(vec.begin() + a, vec.begin() + b);

와 같은 방식으로 a부터 b - 1번째 원소들만 정렬할 수 있습니다.

이번엔 세번째 인자에 대해 알아봅시다.

sort함수가 수행될 때, 어떤 기준으로 정렬이 될 지 정해주는 부분입니다.정의하는 방법은 세 가지 정도 있지만, 가볍게 함수로 정의하는 방법만 보겠습니다.

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

bool compare(int& a, int& b){
	// (a보다 b가 더 크면 true, 아니면 false) == 오름차순
	return a < b;
}

int arr[5] = {4, 3, 2, 1, 0};
vector<int> vec = {4, 3, 2, 1, 0};

int main(){
	
	sort(arr, arr + 5, compare);
	sort(vec.begin(), vec.end(), compare);
	
	return 0;
}

보시는 것처럼 간단합니다. 같은 자료형 두 개를 인자로 받고, bool값을 리턴해주는 함수를 작성해주면 비교함수 완성. 

return a > b; 를 하면 당연하게도 내림차순으로 정렬됩니다.

살짝 tip 아닌 tip을 드리자면 STL에서 제공하는 functional 라이브러리 안에 less<자료형>()과 greater<자료형>() 함수가 있습니다. 매번 compare함수를 작성하는게 귀찮으신 분들은 이 두 함수를 이용하셔도 되지만, 단순한 내림차순 오름차순 정렬임을 유의해주셔야합니다. 

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

int arr[5] = {4, 3, 2, 1, 0};

int main(){
	
	sort(arr, arr + 5, less<int>()); // 오름차순
	sort(arr, arr + 5, greater<int>()); // 내림차순
	
	return 0;
}

자신이 개발자를 준비중이라면,

\(O(n^2)\) : 버블 정렬, 삽입 정렬, 선택 정렬

\(O(nlogn)\) : 힙 정렬(Heap Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 

정도는 스스로 구현할 줄 알아야 한다고 개인적으로 생각합니다. 

하지만, 알고리즘 문제를 해결할 때마다 구현하는 것은 굉장한 시간 낭비일 것입니다. 따라서 저는 algorithm 라이브러리에서 제공하는 sort함수를 사용하여 12단계의 문제들을 해결할 예정입니다.

제가 올리는 글에선 sort함수 사용방법을 배우시고, 만약 위에 언급된 6개 정렬 중 모르는 것이 있다면 꼭 공부해보시는 것을 추천드립니다.

백준에서 제공하는 일반적인 알고리즘 문제에선 sort 함수로도 충분히 통과가 가능하지만, 삼성 B형 테스트와 같이 메모리와 시간 최적화가 필요한 문제들은 스스로 정렬 알고리즘을 구현할 줄 알아야 하기 때문입니다. 시간이 허락한다면, 저도 제가 구현한 코드를 사용하여 문제들을 해결해보도록 하겠습니다. 감사합니다.