C언어가 가지는 장점 중 하나는 연산속도가 빠르다는 것인데요, 이 장점을 이용해 여러가지 배정 문제를 생각보다 많은 반복문을 이용해서도 무난히 해결할 수 있습니다. 배정 문제 중 대표적인 응용분야는 바로 학생들의 시간표를 배정하는 문제인데요, 이번 포스팅에서는 제가 직접 의뢰받았던 시간표 배정 문제를 C언어를 통해 해결한 것을 정리해보도록 하겠습니다.
문제 상황
89명의 학생들이 12개의 수업 중 3개를 각각 선택해서 듣는 상황입니다. 구해야 하는 것은 12개의 수업을 최소 시간만 열어서 모든 학생들이 1~3교시동안 모든 3가지의 수업을 들을 수 있도록 하는 것입니다. 12개의 수업을 3교시 모두 open 한다면 각 교시에 수강하는 사람 수가 너무 적다는 문제가 발생해 비효율이 발생하고, 그렇다고 너무 적은 수의 수업만 open 한다면 3가지의 수업을 3교시동안 모두 못 듣는 학생이 발생할 수 있습니다. 따라서 모든 학생들의 3교시동안 자신의 수업을 들으면서, 가장 효율적인 개설을 위해서는 시간표를 어떻게 짜야할지 탐색해야 합니다.
입력
입력은 txt 파일로 주어집니다. 위와 같이 12개의 전공분야 수업 중 3개가 89줄까지 저장되어 있습니다. 각 줄은 각 학생이 지망하는 3개의 수업입니다. 입력 자체는 excel 파일에서 긁어온 것이므로 C 프로그램 내에서 문자열을 어느 정도 정리하여 조작해줄 필요가 있습니다.
* 아래 첨부파일에 input 파일을 첨부해두었습니다.
출력
모든 학생들의 3교시동안 3가지 수업을 모두 들을 수 있도록 하면서, 수업의 수가 가장 개설이 적게 되는 시간표를 만들어 개설 시간표와 89명의 학생들 각각의 시간표를 구해주어야 합니다. (출력이 워낙 많기 때문에 저 같은 경우에는 파일 출력을 사용하여 txt 파일로 출력되도록 제작하였습니다.)
해결
먼저 C언어로 작성한 코드의 전문은 다음과 같습니다. 접힌 부분을 펼쳐서 확인해보시기 바랍니다. 직접 복사/붙여넣기 하여 실행해보셔도 좋습니다.
#include<stdio.h>
#include<string.h>
#define STUNUM 89
int converter(char word[]) {
if(!strcmp(word, "컴퓨터공학부")) return 1;
else if(!strcmp(word, "기계공학부")) return 2;
else if(!strcmp(word, "항공공학과")) return 3;
else if(!strcmp(word, "건축학과")) return 4;
else if(!strcmp(word, "건설환경공학부")) return 5;
else if(!strcmp(word, "전기/정보공학부")) return 6;
else if(!strcmp(word, "화학생물공학부")) return 7;
else if(!strcmp(word, "재료공학부")) return 8;
else if(!strcmp(word, "에너지자원공학과")) return 9;
else if(!strcmp(word, "원자핵공학과")) return 10;
else if(!strcmp(word, "산업공학과")) return 11;
else if(!strcmp(word, "조선해양공학과")) return 12;
else return 0;
}
void counter(int addr[]) {
if(*addr == 0 && *(addr+1) == 1 && *(addr+2) == 1) *addr = 1, *(addr+1) = 0, *(addr+2) = 1;
else if(*addr == 1 && *(addr+1) == 0 && *(addr+2) == 1) *addr = 1, *(addr+1) = 1, *(addr+2) = 0;
else if(*addr == 1 && *(addr+1) == 1 && *(addr+2) == 0) *addr = 0, *(addr+1) = 0, *(addr+2) = 1;
else if(*addr == 0 && *(addr+1) == 0 && *(addr+2) == 1) *addr = 0, *(addr+1) = 1, *(addr+2) = 0;
else if(*addr == 0 && *(addr+1) == 1 && *(addr+2) == 0) *addr = 1, *(addr+1) = 0, *(addr+2) = 0;
else if(*addr == 1 && *(addr+1) == 0 && *(addr+2) == 0) *addr = 0, *(addr+1) = 1, *(addr+2) = 1;
}
int main() {
char word[20];
char subject_name[13][20] = {"", "컴퓨터공학부", "기계공학부", "항공공학과", "건축학과", "건설환경공학부", "전기/정보공학부",
"화학생물공학부", "재료공학부", "에너지자원공학과", "원자핵공학과", "산업공학과", "조선해양공학과"};
int student[STUNUM][3];
int timetable[13][3] = {{}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}, {0, 1, 1}};
int student_timetable[STUNUM][3];
int flag = 1, count = 0, one_counter = 0;
FILE *fp = fopen("apply.txt", "r");
FILE *fp2 = fopen("allocate.txt", "w");
for(int i=0; i<STUNUM; i++) {
for(int j=0; j<3;) {
fscanf(fp, "%s", word);
if(converter(word)) {
student[i][j] = converter(word);
j++;
}
}
}
while(1) {
counter(timetable[1]);
while(1) {
counter(timetable[2]);
while(1) {
counter(timetable[3]);
while(1) {
counter(timetable[4]);
while(1) {
counter(timetable[5]);
while(1) {
counter(timetable[6]);
while(1) {
counter(timetable[7]);
while(1) {
counter(timetable[8]);
while(1) {
counter(timetable[9]);
while(1) {
counter(timetable[10]);
while(1) {
counter(timetable[11]);
while(1) {
counter(timetable[12]);
flag = 1;
for(int i=0; i<STUNUM; i++) {
if(timetable[student[i][0]][0] && timetable[student[i][1]][1] && timetable[student[i][2]][2]) {
student_timetable[i][0] = student[i][0];
student_timetable[i][1] = student[i][1];
student_timetable[i][2] = student[i][2];
}
else if(timetable[student[i][0]][0] && timetable[student[i][1]][2] && timetable[student[i][2]][1]) {
student_timetable[i][0] = student[i][0];
student_timetable[i][2] = student[i][1];
student_timetable[i][1] = student[i][2];
}
else if(timetable[student[i][0]][1] && timetable[student[i][1]][0] && timetable[student[i][2]][2]) {
student_timetable[i][1] = student[i][0];
student_timetable[i][0] = student[i][1];
student_timetable[i][2] = student[i][2];
}
else if(timetable[student[i][0]][1] && timetable[student[i][1]][2] && timetable[student[i][2]][0]) {
student_timetable[i][1] = student[i][0];
student_timetable[i][2] = student[i][1];
student_timetable[i][0] = student[i][2];
}
else if(timetable[student[i][0]][2] && timetable[student[i][1]][0] && timetable[student[i][2]][1]) {
student_timetable[i][2] = student[i][0];
student_timetable[i][0] = student[i][1];
student_timetable[i][1] = student[i][2];
}
else if(timetable[student[i][0]][2] && timetable[student[i][1]][1] && timetable[student[i][2]][0]) {
student_timetable[i][2] = student[i][0];
student_timetable[i][1] = student[i][1];
student_timetable[i][0] = student[i][2];
}
else {
flag = 0;
// printf("학생 %d : %d %d %d 다 못 들음\n", i, subject_name[student[i][0]], subject_name[student[i][1]], subject_name[student[i][2]]);
break;
}
}
if(flag) {
one_counter = 0;
for(int i=1; i<=12; i++)
for(int j=0; j<3; j++)
if(timetable[i][j]) one_counter++;
if(one_counter < 20) {
for(int i=1; i<=12; i++) {
for(int j=0; j<3; j++) {
printf("%d ", timetable[i][j]);
}
printf(" ");
}
printf("%d\n", one_counter);
count++;
fprintf(fp2, "<경우 %d>\n\n", count);
for(int j=0; j<3; j++) {
fprintf(fp2, "%d교시 : ", j+1);
for(int i=1; i<=12; i++) if(timetable[i][j]) fprintf(fp2, "%s ", subject_name[i]);
fprintf(fp2, "\n");
}
fprintf(fp2, "%28s%20s%20s\n", "1교시", "2교시", "3교시");
for(int i=0; i<STUNUM; i++)
fprintf(fp2, "학생 %2d : %20s%20s%20s\n", i+1, subject_name[student_timetable[i][0]], subject_name[student_timetable[i][1]], subject_name[student_timetable[i][2]]);
fprintf(fp2, "\n\n\n");
}
/*
printf("%28s%20s%20s\n", "1교시", "2교시", "3교시");
for(int i=0; i<STUNUM; i++) {
printf("학생 %2d : %20s%20s%20s\n", i+1, subject_name[student_timetable[i][0]], subject_name[student_timetable[i][1]], subject_name[student_timetable[i][2]]);
}
*/
}
if(!timetable[12][0] && timetable[12][1] && timetable[12][2]) break;
}
if(!timetable[11][0] && timetable[11][1] && timetable[11][2]) break;
}
if(!timetable[10][0] && timetable[10][1] && timetable[10][2]) break;
}
if(!timetable[9][0] && timetable[9][1] && timetable[9][2]) break;
}
if(!timetable[8][0] && timetable[8][1] && timetable[8][2]) break;
}
if(!timetable[7][0] && timetable[7][1] && timetable[7][2]) break;
}
if(!timetable[6][0] && timetable[6][1] && timetable[6][2]) break;
}
if(!timetable[5][0] && timetable[5][1] && timetable[5][2]) break;
}
if(!timetable[4][0] && timetable[4][1] && timetable[4][2]) break;
}
if(!timetable[3][0] && timetable[3][1] && timetable[3][2]) break;
}
if(!timetable[2][0] && timetable[2][1] && timetable[2][2]) break;
}
if(!timetable[1][0] && timetable[1][1] && timetable[1][2]) break;
}
printf("가능한 총 경우의 수 : %d\n", count);
}
가장 먼저 입력의 경우 파일 포인터를 이용하여 파일을 열어주고, 띄어쓰기를 구분하여 단어 단위로 문자열을 읽었습니다. 다만 일부 학과의 경우 괄호를 포함한 필요없는 문자열이 있기 때문에 해당 문자열은 예외처리 해주었습니다.
그 다음 각 학과에 해당하는 문자열에 임시적으로 번호를 부여하였고, 각 input file로부터 정보를 입력받아 배열에 int형으로 저장하였습니다.
이제 배정을 해야하는데 각 수업을 3교시 중 한 교시 또는 두 교시를 연다면 3C1+3C2 = 6가지의 경우가 있고, 이것을 모든 12가지 학과에 대해서 탐색하더라도 6^12 정도의 연산이 반복되기 때문에 충분히 가능할 것이라고 생각하여 brute-force 탐색방법을 사용하였습니다.
void counter(int addr[]) {
if(*addr == 0 && *(addr+1) == 1 && *(addr+2) == 1) *addr = 1, *(addr+1) = 0, *(addr+2) = 1;
else if(*addr == 1 && *(addr+1) == 0 && *(addr+2) == 1) *addr = 1, *(addr+1) = 1, *(addr+2) = 0;
else if(*addr == 1 && *(addr+1) == 1 && *(addr+2) == 0) *addr = 0, *(addr+1) = 0, *(addr+2) = 1;
else if(*addr == 0 && *(addr+1) == 0 && *(addr+2) == 1) *addr = 0, *(addr+1) = 1, *(addr+2) = 0;
else if(*addr == 0 && *(addr+1) == 1 && *(addr+2) == 0) *addr = 1, *(addr+1) = 0, *(addr+2) = 0;
else if(*addr == 1 && *(addr+1) == 0 && *(addr+2) == 0) *addr = 0, *(addr+1) = 1, *(addr+2) = 1;
}
이 때 counter 함수를 사용하여 가장 각 수업에 대해 위에서 언급한 6가지 경우를 각각 돌려줄 수 있도록 하였습니다. 코드 전문을 보시면 아시겠지만 6번 반복하는 반복문을 12중으로 구현할 때 코드를 그나마 줄이고자 counter 함수를 도입하였음을 확인하실 수 있습니다.
그 다음 모든 학생에 대해 현재 반복문 루프에서의 시간표가 적절한지 검사하는 과정을 거칩니다. 만약 적절하다면, 이것이 최소 개수로 열린 수업인지 검사합니다. 저는 해만 구하면 되었기 때문에 코드를 여러 번 돌려서 19번이 최소임을 확인할 수 있었습니다. (코드에 공백이 워낙 많다보니 위의 코드 전문을 확인해주시면 좋을 것 같습니다.)
모든 수업이 통틀어 최소 회수로 열리는 시간표라면 이제 각 학생에 대한 시간표와, 각 시간에 어떤 수업이 열리는지를 파일 입출력을 통해 기록해줍니다.
결과
우선 위와 같이 모든 경우의 수를 탐색하여 모든 수업이 통틀어 19번 열리는 경우를 찾은 뒤 터미널로 출력합니다. 이것은 임시적으로 구별을 하기 위해 작성한 코드이기 때문에 중요한 출력은 아니지만, 각 0과 1이 나타내는 것은 예를 들어 1 0 0은 해당 학부의 수업이 1교시에만 열어도 모든 학생들이 수업을 들을 수 있음을 의미합니다. 36개의 숫자는 3개씩 12개의 묶음으로 나뉘는데 이 12개의 묶음이 각 학부의 수업을 의미합니다.
탐색이 종료되면 위와 같이 총 258가지의 결과가 나옵니다. 6^12 = 약 21억 가지 탐색 중 258가지 결과가 나왔다는 것은 대략적으로 적절한 탐색 결과임을 검증해주는 수치입니다. 다만, 모든 시간표들은 각각 1, 2, 3교시가 서로 바뀔 수 있으므로 실제로는 258/3! = 43가지의 꼴의 조합만이 존재함을 확인할 수 있습니다. 나머지는 서로 위치를 바꿔서 똑같이 만들어질 수 있는 시간표입니다.
이렇게 C언어로 시간표를 제작해보았는데, 사실 우리 실생활에서 발생하는 문제들은 워낙 그 다양성이 크고 상황에 따라 변수가 많기 때문에 이 코드는 참고용으로 확인해주시면 좋을 것 같습니다. 만약 12개의 수업보다 많은 수업이거나 시간표의 교시 수가 3교시 이상일 때 시간표 배정 문제가 발생한다면 그 때는 다른 알고리즘을 사용해야할 수도 있습니다.
'기타' 카테고리의 다른 글
| [백준/BOJ] 백준 "맞았습니다" 정답 코드 추출, 저장하는 법 (코드 모음 만드는 법) (3) | 2021.12.29 |
|---|---|
| [Zoom] 줌 회의 40분 제한 무료로 푸는 법 (G-Suite 아님 / 2021.12.09 작동 확인) (2) | 2021.12.09 |
| [토익 Voca Test 프로그램] 모르는 단어만 랜덤 반복 초간편 암기 프로그램 (TOEIC 필수 단어 2000개 포함) (1) | 2021.10.25 |
| C언어 반복문 사각형, 삼각형, 평행사변형, 마름모 출력하기 (Codeup) (0) | 2021.01.13 |
| [C언어 반복문] 약수의 합이 자신의 5배를 넘을 수 있을까? (0) | 2021.01.07 |