새터 조 배정 프로그램 제작

문제 상황

N명의 학생을 M개의 조로 나눌 것임.

(100 <= N <= 150, 10 <= M <= 20)

각 학생의 정보는 다음과 같음.
 - 성별: M / F (편의상 각각 1, 2)
 - 반: A / B / C / D (편의상 각각 1, 2, 3, 4)

 - 프락치 여부 (편의상 각각 0, 1) (<= 12)

 - 반참 여부 (편의상 각각 0, 1) (<= 15 예상)

 - (선택) 입학 유형: 수시 / 정시 (편의상 각각 1, 2)

 - 조 고정 여부 (0: 고정 X, t: t조로 고정)

 

파싱은 파이썬으로 -> 생각보다 어려움

그냥 손으로 하자

각 조에 모든 정보가 최대한 고르도록 조를 편성하고 싶음.
편성하는 방법 및 알고리즘?

- SA는 됨
- Ramdom이 됨?
- Brute Force가 됨?
- 남자 여자로 나눠서 MITM?
- 남자 여자 각각 균일하게 만들고 잘 합치면?

 

 

알고리즘

 

가장 뇌를 안 쓰고 좋은 결과를 얻을 수 있는 SA(Simulated Annealing)을 선택.

근데 이것도 뇌를 써야 함

 

일단 처음에 수만 균일하게 무작위적으로 배정.

이후 조가 다른 두 명의 조를 바꿔보면서 SA를 진행함.

scoring이 중요한데, 각 factor가 균일하게 퍼져 있을수록 낮은 점수를 줄 것임.

이는 각 조의 각 factor의 수의 제곱을 모두 더하면 자연스럽게 해결.

-> 대충 이차함수나 코시-슈바르츠로 설명 가능

근데 여기서 factor마다 가중치를 주면 factor 간의 우열을 만들 수 있음

 

 

사용 방법

 

입력

- 첫째 줄에 학생 수($N$)와 조 개수($M$)을 공백으로 구분하여 입력한다. (신입생 + 프락치)

- 둘째 줄부터 $N$개의 줄에 걸쳐 학생의 정보를 입력한다.

- 학생의 정보는 이름, 학번, 성별, 반, 프락치 여부, 반참 여부, 조 고정 여부로 구성한다.

 

- 성별: [남자, 여자] 각각 [1, 2] 입력

- 반: [나래, 라온, 여우비, 해밀] 각각 [1, 2, 3, 4] 입력

- 프락치: [X, O] 각각 [0, 1] 입력

- 반참: [X, O] 각각 [0, 1] 입력

- 조: 이미 조가 있을 시 해당 조, 아니면 [0] 입력

 

팁

- 최대 학생 수, 반 수 등이 달라진다면 코드 윗부분의 상수와 명칭을 수정하면 된다.

- 정보의 가중치를 원하는대로 변경해도 된다. 단, 10,000이 넘으면 문제가 생길 수 있다.

- 학생 구조체를 바꿔도 되는데, 그러려면 코드 전체적으로 수정이 필요하다.

- 나이를 고려하지 못했다. 나이를 고려하는 건 방향성이 달라서 어렵다.

- 전형은 고려하지 않았는데, 수시를 먼저 배정하고 정시를 추가하면 잘 섞일 거라 기대된다.

- 결과가 마음에 들지 않으면 여러 번 돌려보면 된다. 매번 결과가 달라진다.

 

 

코드

 

language: c++17

#include <bits/stdc++.h>
#include <random>
using namespace std;

const int N = 200; // 최대 학생수 (여유)
const int G = 2; // 성별 수
const int C = 4; // 반 수
// 프락치, 반참 구분은 (0/1)로 고정

// 각 정보의 가중치
const int GVAL = 10;
const int CVAL = 8;
const int FVAL = 30;
const int HVAL = 50;

// 각 정보의 명칭
vector<string> gender_name = {"", "남자", "여자"};
vector<string> cls_name = {"", "나래", "라온", "여우비", "해밀"};

// 랜덤 함수
struct Random {
   mt19937 rd;
   Random() : rd((unsigned)chrono::steady_clock::now().time_since_epoch().count()) {}
   Random(int seed) : rd(seed) {}
   template<typename T = int> T GetInt(T l = 0, T r = 32767) {
      return uniform_int_distribution<T>(l, r)(rd);
   }
   template<typename T = double> T GetDouble(T l = 0, T r = 1) {
      return uniform_real_distribution<T>(l, r)(rd);
   }
} Rand;

// 학생 정보 구조체
struct student {
    string name, id; // 이름, 학번
    int gender, cls, frak, half, fix; // 성별, 반, 프락치, 반참, 조
} a[N];

int n, m, sz, group[N], ans[N], mn = 1e9;
vector<int> notfix;

// SA 보조 함수
int scoring() {
    int ret = 0;
    for (int j = 1; j <= m; j++) {
        int gender[G + 1] = {}, cls[C + 1] = {}, frak[2] = {}, half[2] = {};
        for (int i = 1; i <= n; i++) if (group[i] == j) {
            gender[a[i].gender]++, cls[a[i].cls]++, frak[a[i].frak]++, half[a[i].half]++;
        }
        for (int i = 1; i <= G; i++) ret += GVAL * gender[i] * gender[i];
        for (int i = 1; i <= C; i++) ret += CVAL * cls[i] * cls[i];
        ret += FVAL * frak[1] * frak[1];
        ret += HVAL * half[1] * half[1];
    }
    return ret;
}

// SA
void simulated_annealing() {
    double t = 1, d = 0.9999, k = 10, lim = 0.0001; // SA 변수들
    for (; t > lim; t *= d) {
        int e1 = scoring();
        int x = notfix[Rand.GetInt(0, sz - 1)], y = x;
        while (group[x] == group[y]) y = notfix[Rand.GetInt(0, sz - 1)];
        swap(group[x], group[y]);
        int e2 = scoring();

        double p = exp((e1 - e2) / (k * t));
        if (p < Rand.GetDouble()) swap(group[x], group[y]);
        int ret = scoring();
        if (ret < mn) {
            for (int i = 1; i <= n; i++) ans[i] = group[i];
            mn = ret;
        }
    }
}

int main()
{
    cin >> n >> m; // 학생 수, 조 개수
    for (int i = 1; i <= n; i++) {
        auto &st = a[i];
        
        st.name = "학생" + to_string(i);
        st.id = to_string(2024000 + i);
        st.gender = Rand.GetDouble() < 0.65 ? 1 : 2;
        st.cls = Rand.GetInt(1, 4);
        st.frak = Rand.GetDouble() < 0.04;
        st.half = Rand.GetDouble() < 0.05;
        if (st.frak) st.half = 0;
        st.fix = 0;

        // cin >> st.name >> st.id;
        // cin >> st.gender >> st.cls >> st.frak >> st.half >> st.fix;
    }
    
    vector<int> cnt(m + 1), grps;
    for (int i = 1; i <= n; i++) {
        if (a[i].fix) cnt[a[i].fix]++, group[i] = a[i].fix;
        else notfix.push_back(i);
    }
    sz = notfix.size();
    for (int i = 1; i <= m; i++) grps.push_back(i);
    sort(grps.begin(), grps.end(), [&](int i, int j){ return cnt[i] < cnt[j]; });
    for (int i = 0; i < sz; i++) group[notfix[i]] = grps[i % m];

    if (sz > 1) simulated_annealing();

    // 각 조의 정보 출력
    for (int j = 1; j <= m; j++) {
        cout << "Group " << j << ": \n";

        int gender[G + 1] = {}, cls[C + 1] = {}, frak[2] = {}, half[2] = {};
        for (int i = 1; i <= n; i++) if (ans[i] == j) {
            cout << a[i].name << ' ' << a[i].id << '\n';
            gender[a[i].gender]++, cls[a[i].cls]++, frak[a[i].frak]++, half[a[i].half]++;
        }

        for (int i = 1; i <= G; i++) cout << gender_name[i] << ": " << gender[i] << (i < G ? " / " : "\n");
        for (int i = 1; i <= C; i++) cout << cls_name[i] << ": " << cls[i] << (i < C ? " / " : "\n");
        cout << "프락치: " << frak[1] << '\n';
        cout << "반참: " << half[1] << "\n\n";
    }

    // 새로 배정된 학생 정보 출력
    for (int i = 1; i <= n; i++) if (!a[i].fix) {
        cout << a[i].name << ' ' << a[i].id << ' ' << group[i] << '\n';
    }
}