[Algorithm] 2주차 스터디 - 정렬

주제 : 정렬 (sort)

c++의 sort() 함수

C++ STL 함수의 sort() 함수는 quick sort 알고리즘을 바탕으로 만들어졌다. 최악의 경우에 대해서도 어느 정도 개선된 quick sort 알고리즘이라고 할 수 있다. 따라서 대부분의 경우  O(n*logn) 의 시간복잡도를 가진다.

 

sort() 함수 사용법

C++의 algorithm 헤더에 sort() 함수가 포함되어 있다. 사용 방법은 다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int a[10] = {9, 3, 5, 4, 1, 10, 8, 5, 7, 2};
    sort(a, a + 10);
    for (int i = 0; i < 10; i++) {
    	cout << a[i] << ' ';
    }
}

sort() 함수는 오름차순이 기본이다. 따라서 해당 코드의 결과는 다음과 같다.

1 2 3 4 5 5 7 8 9 10

 

다음은 sort() 함수의 정렬방식에 따른 코드 구현 방법이다.

1. sort(배열의 시작점 주소, 배열의 마지막 주소 + 1) 이면 오름차순 정렬
2. sort(배열의 시작점 주소, 배열의 마지막 주소 + 1, greater<>()) 이면 내림차순 정렬
3. sort(배열의 시작점 주소, 배열의 마지막 주소 + 1, compare) 이면 사용자 정의 함수로 정렬

 

+ merge sort란

이번 2주차 스터디 필수 문제 중에 merge sort를 알면 쉽게 풀 수 있는 문제가 있다. 잘 정리해놓은 글을 발견해서 참고자료로 올린다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

 

---

필수 문제 풀이

백준 2751 - 수 정렬하기 2 (C++)

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 문제이다.

풀이

C++ STL에서 sort() 함수를 제공하고 있다. 따라서 이 함수를 사용하면 아주 간단하게 오름차순과 내림차순으로 정렬할 수 있다. 여담으로 요즘 클린코드에 관한 수업을 듣고 있는데 intent를 먼저 전달하는 코드가 좋은 코드라고 배웠다. 그래서 입력받는 부분과 결과를 출력하는 부분을 inputData()와 print() 함수로 따로 빼서 코드를 짜봤다. 

제출한 코드

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

vector<int> inputData() {
	int total;
	int number;
	vector<int> inputNumber;

	cin >> total;
	for (int i = 0; i < total; i++) {
		cin >> number;
		inputNumber.push_back(number);
	}
	return inputNumber;
}

void print(vector<int> &vector) {
	for (int i = 0; i < vector.size(); i++) {
		cout << vector[i] << "\n";
	}
}

int main() {
	vector<int> input = inputData();
	sort(input.begin(), input.end());
	print(input);
	return 0;
}

 

백준 10825 - 국영수 (C++)

https://www.acmicpc.net/problem/10825

10825번: 국영수

학생 N명의 이름과 국어, 영어, 수학 점수가 주어질 때,

1. 국어 점수가 감소하는 순서로
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 대문자가 앞에 온다)

이와 조건으로 학생의 성적을 정렬하는 문제이다.

풀이

구조체를 사용하여 코드 전체에 걸쳐 자주 참조하는 변수를 선언했다. 구조체를 사용하면 함수에 데이터를 넘길 때 해당 구조체만 넘겨주면 된다. 이렇게 하면, 후에 참조되는 함수에 파라미터를 추가하더라도 함수의 선언을 바꾸지 않고도 전달 하고자 하는 데이터를 바꿀 수 있다는 장점이 있기 때문이다. 그리고 문제 조건에 맞게 정렬할 수 있는 compare() 함수를 짰다. compare 함수를 보면 if문이 비슷하게 반복되고 있기에 후에 리팩토링을 하면 더 깔끔한 코드가 될 수 있을 것 같다.

제출한 코드

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

struct Student {
	string name;
	int korean;
	int english;
	int math;
};

vector<Student> inputData() {
	int n;
	Student s;
	vector<Student> student;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s.name >> s.korean >> s.english >> s.math;
		student.push_back(s);
	}
	return student;
}

bool compare(Student &a, Student &b) {
	if (a.korean == b.korean) {
		if (a.english == b.english) {
			if (a.math == b.math) {
				return a.name < b.name;
			}
			else {
				return a.math > b.math;
			}
		}
		else {
			return a.english < b.english;
		}
	}return a.korean > b.korean;
}

void print(vector<Student>& vector) {
	for (int i = 0; i < vector.size(); i++) {
		cout << vector[i].name << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	vector<Student> studentCopy = inputData();
	sort(studentCopy.begin(), studentCopy.end(), compare);
	print(studentCopy);
}

 

백준 11582 - 치킨 TOP N (C++)

https://www.acmicpc.net/problem/11582

11582번: 치킨 TOP N

무작위로 있는 N개의 치킨 맛 수치를 N/2명이 차례대로 2개의 치킨집을 선택해  정렬을 한다. 그 뒤 N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택 하여 치킨집을 정렬을 한다. 계속해서 N/8명, N/16명이 정렬을 진행하다가 마지막 사람이 두 개의 정렬된 그룹을 합병하여 완료하는 방식이다. k명이 정렬할 때, 그때까지의 정렬 결과를 구하는 문제이다.

풀이

전형적인 merge sort 문제이다. 보다 객체지향적인 프로그래밍을 하고 싶어서 class를 사용하여 필요한 변수와 함수를 선언한 뒤, merge sort 코드를 사용하여 코드를 짰다. 다만, 이 문제는 일반 merge sort와는 다르게 해당 조건을 만족하는 순간 정렬을 멈춰야 하므로 merge 함수에 if ((right - left) > (store / targetMember)) return; 코드를 추가해준다.

제출한 코드

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

class Chicken {
public:
	int store;
	vector<int> chickenRanking;
	int targetMember;

	void mergeSort(vector<int>&, int, int);
	void merge(vector<int>&, int, int, int);
	void mergeTest();
	void print();
};

void Chicken::merge(vector<int>& nums, int left, int middle, int right) {
	if ((right - left) > (store / targetMember)) return;
	vector<int> tmp(right - left + 1);
	int i = left;
	int j = middle + 1;
	int k = 0;

	while (i <= middle && j <= right) {
		if (nums[i] <= nums[j])
			tmp[k++] = nums[i++];
		else
			tmp[k++] = nums[j++];
	}

	while (i <= middle) tmp[k++] = nums[i++];
	while (j <= right) tmp[k++] = nums[j++];
}

void Chicken::mergeSort(vector<int>& nums, int left, int right) {
	if (left >= right) return;
	int middle = left + (right - left) / 2;
	mergeSort(nums, left, middle);
	mergeSort(nums, middle + 1, right);
	merge(nums, left, middle, right);
}

void Chicken::print() {
	for (int i = 0; i < store; i++) {
		cout << chickenRanking[i] << ' ';
	}
}

int main() {
	ios::sync_with_stdio(false);
	int n, k;
	vector<int> v;

	Chicken chicken;
	cin >> n;
	chicken.store = n;
	int number;

	for (int i = 0; i < n; i++) {
		cin >> number;
		v.push_back(number);
	}
	chicken.chickenRanking = v;
	cin >> k;
	chicken.targetMember = k;

	chicken.mergeSort(chicken.chickenRanking, 0, chicken.store - 1);
	chicken.print();

	return 0;
}

 

Reference

• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ksgkms26&logNo=221320183662
• https://d2.naver.com/helloworld/0315536
• https://blog.naver.com/ndb796/221227975229
• https://ingorae.tistory.com/1444