알고리즘 c++ 코드 두개를 하나로 합쳐주세요.
-
게시물 수정 , 삭제는 로그인 필요
첫번째 코드입니다
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
// 구조체 정의
struct ScoreIndex {
int score;
int index;
};
// 비교 함수 정의 (내림차순)
bool compareScore(const ScoreIndex& lhs, const ScoreIndex& rhs) {
return lhs.index > rhs.index;
}
// 그룹 생성 함수
int createGroups(int students, int groups, int arr[]) {
// 점수를 내림차순으로 정렬
std::sort(arr, arr + students, std::greater<int>());
int studentsgap[students - 1];
int floor = 0;
int **answer = new int*[groups];
if (answer == nullptr) {
exit(1);
}
for (int i = 0; i < groups; i++) {
answer[i] = new int[students];
if (answer[i] == nullptr) {
exit(1);
}
}
for (int i = 0; i < students - 1; i++) {
studentsgap[i] = arr[i] - arr[i + 1];
}
std::sort(studentsgap, studentsgap + students - 1, std::greater<int>());
int studentCount = 1;
for (int i = 0; i < students; i++) {
if (i != students - 1) {
if (studentsgap[floor] == arr[i] - arr[i + 1] && floor < groups - 1) {
answer[floor][i] = studentCount++;
floor++;
} else {
answer[floor][i] = studentCount++;
}
} else {
answer[groups - 1][i] = studentCount++;
}
}
// 결과 출력 및 Partition1.txt 파일에 저장
std::ofstream outputFile("Partition1.txt");
int total = 0;
for (int i = 0; i < groups - 1; i++) {
total += studentsgap[i];
}
if (!outputFile.is_open()) {
exit(1);
}
for (int i = 0; i < groups; i++) {
for (int j = 0; j < students; j++) {
if (answer[i][j] != 0) {
outputFile << answer[i][j] << "(" << arr[j] << ") ";
}
}
outputFile << std::endl;
}
outputFile.close();
for (int i = 0; i < groups; i++) {
delete[] answer[i];
}
delete[] answer;
return total;
}
int main() {
int students, groups;
std::cin >> students >> groups;
int *arr = new int[students];
if (arr == nullptr) {
return 1;
}
for (int i = 0; i < students; i++) {
std::cin >> arr[i];
}
int differenceSum = createGroups(students, groups, arr);
std::cout << differenceSum << std::endl;
delete[] arr;
return 0;
두번째 코드입니다
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <utility>
#include <limits>
// 구조체 정의
struct ScoreIndex {
int score;
int index;
};
// 비교 함수 정의
bool compareScore(const ScoreIndex& lhs, const ScoreIndex& rhs) {
return lhs.score > rhs.score; // 내림차순 정렬
}
// 그룹별로 분산을 계산하는 함수
double calculateVariance(const std::vector<ScoreIndex>& group) {
int n = group.size();
if (n <= 1) // 그룹에 한 명 이상의 학생이 있어야 함
return 0.0;
double sum = 0.0;
for (const auto& student : group) {
sum += student.score;
}
double mean = sum / n;
double variance = 0.0;
for (const auto& student : group) {
variance += (student.score - mean) * (student.score - mean);
}
variance /= n; // 개수로 나누기
return variance;
}
// 그룹을 생성하는 함수
std::vector<std::vector<ScoreIndex> > createGroups(const std::vector<int>& scores, int k) {
std::vector<std::vector<ScoreIndex> > groups(k);
// 점수와 인덱스를 가진 구조체로 데이터 구성
std::vector<ScoreIndex> scoreIndex;
for (int i = 0; i < scores.size(); ++i) {
ScoreIndex si;
si.score = scores[i];
si.index = i + 1;
scoreIndex.push_back(si);
}
// 내림차순으로 정렬
std::sort(scoreIndex.begin(), scoreIndex.end(), compareScore);
// 각 그룹에 학생 배정
for (const auto& student : scoreIndex) {
int minGroup = -1;
double minVariance = std::numeric_limits<double>::max();
for (int i = 0; i < k; ++i) {
groups[i].push_back(student);
double variance = calculateVariance(groups[i]);
if (variance < minVariance) {
minVariance = variance;
minGroup = i;
}
groups[i].pop_back(); // 다음 그룹을 위해 학생 제거
}
groups[minGroup].push_back(student); // 최소 분산을 가진 그룹에 학생 배정
}
return groups;
}
int main() {
int n, k;
std::cin >> n >> k;
if (n <= k) { // k가 n보다 커야 함
return 1;
}
if (n > 10000 || k > 12) { // n은 10의 4승보다 커서는 안되고 k도 12보다 커서는 안됨
return 1;
}
std::vector<int> scores(n);
for (int i = 0; i < n; ++i) {
std::cin >> scores[i];
}
// 그룹을 생성
auto groups = createGroups(scores, k);
// 출력 파일에 그룹 및 해당 점수 출력
std::ofstream outfile("Partition2.txt");
if (outfile.is_open()) {
for (const auto& group : groups) {
for (const auto& student : group) {
outfile << student.index << "(" << student.score << ") ";
}
outfile << std::endl; // 각 그룹의 학생들이 출력된 후 줄 바꿈
}
outfile.close();
} else {
return 1;
}
// 최소화된 분산의 합 출력
double total_variance = 0.0;
for (const auto& group : groups) {
total_variance += calculateVariance(group);
}
std::cout << total_variance << std::endl;
return 0;
}
출력 결과는 사진처럼 나와야합니다
내일까지 제출인데 너무 안돼서 정신병올걱같아요
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
// 구조체 정의
struct ScoreIndex {
int score;
int index;
};
// 비교 함수 정의 (내림차순)
bool compareScore(const ScoreIndex& lhs, const ScoreIndex& rhs) {
return lhs.index > rhs.index;
}
// 그룹 생성 함수
int createGroups(int students, int groups, int arr[]) {
// 점수를 내림차순으로 정렬
std::sort(arr, arr + students, std::greater<int>());
int studentsgap[students - 1];
int floor = 0;
int **answer = new int*[groups];
if (answer == nullptr) {
exit(1);
}
for (int i = 0; i < groups; i++) {
answer[i] = new int[students];
if (answer[i] == nullptr) {
exit(1);
}
}
for (int i = 0; i < students - 1; i++) {
studentsgap[i] = arr[i] - arr[i + 1];
}
std::sort(studentsgap, studentsgap + students - 1, std::greater<int>());
int studentCount = 1;
for (int i = 0; i < students; i++) {
if (i != students - 1) {
if (studentsgap[floor] == arr[i] - arr[i + 1] && floor < groups - 1) {
answer[floor][i] = studentCount++;
floor++;
} else {
answer[floor][i] = studentCount++;
}
} else {
answer[groups - 1][i] = studentCount++;
}
}
// 결과 출력 및 Partition1.txt 파일에 저장
std::ofstream outputFile("Partition1.txt");
int total = 0;
for (int i = 0; i < groups - 1; i++) {
total += studentsgap[i];
}
if (!outputFile.is_open()) {
exit(1);
}
for (int i = 0; i < groups; i++) {
for (int j = 0; j < students; j++) {
if (answer[i][j] != 0) {
outputFile << answer[i][j] << "(" << arr[j] << ") ";
}
}
outputFile << std::endl;
}
outputFile.close();
for (int i = 0; i < groups; i++) {
delete[] answer[i];
}
delete[] answer;
return total;
}
int main() {
int students, groups;
std::cin >> students >> groups;
int *arr = new int[students];
if (arr == nullptr) {
return 1;
}
for (int i = 0; i < students; i++) {
std::cin >> arr[i];
}
int differenceSum = createGroups(students, groups, arr);
std::cout << differenceSum << std::endl;
delete[] arr;
return 0;
두번째 코드입니다
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <utility>
#include <limits>
// 구조체 정의
struct ScoreIndex {
int score;
int index;
};
// 비교 함수 정의
bool compareScore(const ScoreIndex& lhs, const ScoreIndex& rhs) {
return lhs.score > rhs.score; // 내림차순 정렬
}
// 그룹별로 분산을 계산하는 함수
double calculateVariance(const std::vector<ScoreIndex>& group) {
int n = group.size();
if (n <= 1) // 그룹에 한 명 이상의 학생이 있어야 함
return 0.0;
double sum = 0.0;
for (const auto& student : group) {
sum += student.score;
}
double mean = sum / n;
double variance = 0.0;
for (const auto& student : group) {
variance += (student.score - mean) * (student.score - mean);
}
variance /= n; // 개수로 나누기
return variance;
}
// 그룹을 생성하는 함수
std::vector<std::vector<ScoreIndex> > createGroups(const std::vector<int>& scores, int k) {
std::vector<std::vector<ScoreIndex> > groups(k);
// 점수와 인덱스를 가진 구조체로 데이터 구성
std::vector<ScoreIndex> scoreIndex;
for (int i = 0; i < scores.size(); ++i) {
ScoreIndex si;
si.score = scores[i];
si.index = i + 1;
scoreIndex.push_back(si);
}
// 내림차순으로 정렬
std::sort(scoreIndex.begin(), scoreIndex.end(), compareScore);
// 각 그룹에 학생 배정
for (const auto& student : scoreIndex) {
int minGroup = -1;
double minVariance = std::numeric_limits<double>::max();
for (int i = 0; i < k; ++i) {
groups[i].push_back(student);
double variance = calculateVariance(groups[i]);
if (variance < minVariance) {
minVariance = variance;
minGroup = i;
}
groups[i].pop_back(); // 다음 그룹을 위해 학생 제거
}
groups[minGroup].push_back(student); // 최소 분산을 가진 그룹에 학생 배정
}
return groups;
}
int main() {
int n, k;
std::cin >> n >> k;
if (n <= k) { // k가 n보다 커야 함
return 1;
}
if (n > 10000 || k > 12) { // n은 10의 4승보다 커서는 안되고 k도 12보다 커서는 안됨
return 1;
}
std::vector<int> scores(n);
for (int i = 0; i < n; ++i) {
std::cin >> scores[i];
}
// 그룹을 생성
auto groups = createGroups(scores, k);
// 출력 파일에 그룹 및 해당 점수 출력
std::ofstream outfile("Partition2.txt");
if (outfile.is_open()) {
for (const auto& group : groups) {
for (const auto& student : group) {
outfile << student.index << "(" << student.score << ") ";
}
outfile << std::endl; // 각 그룹의 학생들이 출력된 후 줄 바꿈
}
outfile.close();
} else {
return 1;
}
// 최소화된 분산의 합 출력
double total_variance = 0.0;
for (const auto& group : groups) {
total_variance += calculateVariance(group);
}
std::cout << total_variance << std::endl;
return 0;
}
출력 결과는 사진처럼 나와야합니다
내일까지 제출인데 너무 안돼서 정신병올걱같아요
#알고리즘 c++ #알고리즘 c++ 파이썬 #다익스트라 알고리즘 c++ #크루스칼 알고리즘 c++ #lca 알고리즘 c++ #그리디 알고리즘 c++ #벨만포드 알고리즘 c++ #프림 알고리즘 c++ #브루트포스 알고리즘 c++ #투포인터 알고리즘 c++