EVI$ION 겨울방학 코테스터디 4주차 과제

정렬 알고리즘

선택 정렬

 

삽입 정렬

 

버블 정렬

 

합병 정렬

 

퀵 정렬

 

개념 참고)

https://hsp1116.tistory.com/33

 

---

10825, 국영수, C++

학생 정보 = 구조체 선언

sort( ) 사용 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct student { // 학생 정보 구조체: 이름, 국어 점수, 영어 점수, 수학 점수
	string name;
	int kor, eng, math;
};

// 비교 함수
bool cmpAdv(const student& s1, const student& s2) {
	if (s1.kor != s2.kor) {// 국어 점수가 감소하는 순서
		return s1.kor > s2.kor;
	}
	if (s1.eng != s2.eng) {// (국어 점수가 같으면) 영어 점수가 증가하는 순서
		return s1.eng < s2.eng;
	}
	if (s1.math != s2.math) {// (국어, 영어 점수가 같으면) 수학 점수가 감소하는 순서
		return s1.math > s2.math;
	}
	return s1.name < s2.name; // (국어, 영어, 수학 점수가 같으면) 이름이 사전 순으로 증가하는 순서
}

/*
* 학생 정보를 구조체에 저장
* 정렬 방법을 비교 함수에 추가
*/

int main()
{
	int n;
	vector<student> my_class;
	// 입력
	cin >> n;
	my_class.assign(n, {});
	for (int i = 0; i < n; i++) { // 이름, 국어, 영어, 수학 점수
		cin >> my_class[i].name >> my_class[i].kor >> my_class[i].eng >> my_class[i].math;
	}
	// 연산
	sort(my_class.begin(), my_class.end(), cmpAdv);
	// 출력
	for (int i = 0; i < my_class.size(); i++) {
		cout << my_class[i].name << '\n';
	}
	return 0;
}

 

---

2750, 수 정렬하기, C++

문제) N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	vector<int> st; int N; int Num;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> Num;
		st.push_back(Num);
	}
	sort(st.begin(), st.end(), less<int>());
	for (int i = 0; i < N; i++)
	{
		cout << st[i] << "\n";
	}
	return 0;
}

---

1946, 신입사원, C++

 

각 지원자는 서류 심사 순위와 면접 심사 순위를 가진다.

채용 기준:

1. 서류 심사 기준으로 정렬
2. 이전에 본 지원자들보다 면접 순위가 높은 경우만 채용

채용할 수 있는 최대 지원자 수를 구한다.

 

서류 심사 1등은 무조건 합격시키고

최고 면접 순위를 highest_rank에 저장한다 (초기값: 첫 번째 지원자의 면접 순위)

나머지 지원자들을 순차적으로 확인하면서 

이전보다 면접 순위가 높은 경우(highest_rank > candidate[i].second) 즉시 합격 처리(Cnt++)하고 highest_rank 업데이트한다. 

 

중요한 점:

• 서류 심사 순위 기준으로 정렬했기 때문에, 앞에 있는 지원자들은 서류 순위가 더 높음.
• 따라서, 면접 순위만 비교하면 최적의 방법으로 채용 가능.

첫번째 테스트 케이스(n=5)

- 입력된 지원자 데이터

서류순위	면접순위
3	2
1	4
4	1
2	3
5	5

 

- 서류 순위 기준으로 정렬

서류순위	면접순위
1	4
2	3
3	2
4	1
5	5

• 첫 번째 후보(서류 1위)는 무조건 합격 → cnt = 1, highest_rank = 4
• 두 번째 후보(서류 2위, 면접 3위) → 면접 순위가 highest_rank(4)보다 낮음 → 합격 (cnt = 2)
• 세 번째 후보(서류 3위, 면접 2위) → 면접 순위가 highest_rank(3)보다 낮음 → 합격 (cnt = 3)
• 네 번째 후보(서류 4위, 면접 1위) → 면접 순위가 highest_rank(2)보다 낮음 → 합격 (cnt = 4)
• 다섯 번째 후보(서류 5위, 면접 5위) → 면접 순위가 highest_rank(1)보다 높음 → 불합격

최종 합격자 수: 4

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> ci; // pair<int, int> 를 ci라는 이름으로 정의

int maxEmploy(vector<ci> candidates) {
	// 서류 심사 1등(0번 인덱스)은 무조건 합격
	int cnt = 1, highest_rank = candidates[0].second;
	// i번째 사람은 0 ~ i-1번째 사람보다 서류 심사 순위가 높음
	// 0 ~ i-1번째 사람들 중 면접 순위가 가장 높은 사람보다 면접 순위가 높아야 합격
	for (int i = 1; i < candidates.size(); i++) {
		if (highest_rank > candidates[i].second) { // 이전 사람들보다 면접 순위가 높은 경우
			highest_rank = candidates[i].second; // 가장 높은 면접 순위 갱신
			cnt++; // 합격자 추가
		}
	}
	return cnt;
}

/*
* 서류, 면접 순위 중 하나를 기준(고정)으로 정렬 후 다른 하나의 순위를 비교
* 오름차순으로 정렬 후 위에서부터 순차적으로 비교
*/

int main()
{
	int t, n, cnt;
	// 입력
	cin >> t;
	while (t--) {
		cin >> n;
		vector<ci> candidates(n, ci(0, 0));
		for (int i = 0; i < n; i++) {
			cin >> candidates[i].first >> candidates[i].second; // first: 서류 심사 순위, second: 면접 심사 순위
		}
		// 연산
		sort(candidates.begin(), candidates.end()); // 서류 심사 순위(first) 순서대로 정렬
		cnt = maxEmploy(candidates);
		// 출력
		cout << cnt << '\n';
	}
	return 0;
}