방학 계획 1일차 - 백준 알고리즘 하루에 4문제 풀기(2)

3) 2750번: 수 정렬하기

www.acmicpc.net/problem/2750

2750번: 수 정렬하기

#include <iostream>
using namespace std;
void swap(int &a, int &b);
void bubble(int a[], int size);

int main() {
	int n;
	int a[1000];
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int size = n; size > 1; size--) bubble(a, size);
	for (int i = 0; i < n; i++) cout << a[i] << endl;
}

void swap(int &a, int &b) {
	int temp;
	temp = a;
	a = b;
	b = temp;
}

void bubble(int a[], int size) {
	for (int i = 0; i < size-1; i++) {
		if (a[i] > a[i+1]) swap(a[i], a[i+1]);
	}
}

버블 정렬 어떻게 하는 건지 이미 배웠기 때문에 알고 있어서 쉽게 쓸 수 있었다. 사실 예전에 풀어놨었는데 버블 정렬이면서도 약간 이상하게 꼬아서 풀어가지고 이번 기회에 그 부분을 고쳐보려고 했다. 아직 뇌가 적응을 못하는 느낌이라 예전에 공부했던 내용들 보면서 다시 상기시켰고 틀린 부분을 찾아서 결국 고치기는 했다. 이 문제를 처음 봤을 때는 시간 복잡도가 뭔지 잘 몰랐었는데 지금은 이산수학을 통해 버블 정렬이 O(n^2)의 복잡도를 갖고 있다는 것을 알고 있다. 역시 아는 게 많이지면 보이는 것도 많다고.. 이 다음 문제인 2751번을 풀 때도 똑같은 문제인 줄 알고 버블 정렬로 풀어봤었는데 시간 초과가 떠서 정말 당황스러웠다. (당시에는 시간 복잡도고 뭐고 암것도 몰랐음) 그러나 O(nlogn)의 복잡도를 가진 정렬로 풀어달라는.. 말을 이제야 봐버려서.. 힙정렬이나 병합 정렬로 풀어보고 싶었지만 나의 능력 부족으로 그건 좀 더 공부한 다음에 풀어보도록 해야겠다.(문제에서 요구하던 대로 함수 안에 있는 sort로 풀었음. 아래에 언급)

 

4) 2751번: 수 정렬하기2

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

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

int main() {
	int n, num;
	cin >> n;
	vector<int> a;
	for (int i = 0; i < n; i++) {
		cin >> num;
		a.push_back(num);
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++)
		cout << a[i] <<"\n";
}

사실 vector에 대해서는 이번 방학 때 백준 풀면서 처음 접해봤다. 근데 algorithm이랑 vector는 모르는 코드들 구글링하다보면 정말 많이 쓰고 있다는 것을 보고는 학기 중에 궁금하기는 했었다. 현생에 치여 알아보지는 못했었다는.. 그래서 방학 기념+할 것도 없으니 vector랑 algorithm에 어떤 함수가 있는지랑 어떻게 쓰이는지 등을 좀 알아보고 체감하기로 했다. 사실 최근에 vector 써서 문제 푼 게 있는데 그거 풀면서 좀 늘었던 것 같다. 배열보다 조금 더 편하다고나 할까? 아무튼 사용법을 조금 알기도 했고 언제 쓰면 되는 건지 알게 되니까 2751번 딱 보자마자 sort()함수 사용해야겠다고 퍼뜩 떠올랐다. 그래서 쓰다가 배열이랑 헷갈리고 뭐 여러가지 시행착오가 또 있었지만 결국 풀긴 했다. 쓰면 쓸수록 vector 편리하고 좋은 것 같다.. 아직 초보라 잘 모르긴 하지만 느낌이 그렇다.. ㅋㅋㅋ