Who's next me

배경

학교에서, 선생님에게도 학생들에게도 자리배치는 굉장히 골칫거리인 문제입니다. 학생들이 불만을 가지기 쉽상이며, 학생들이 이러한 불만을 품게 될 경우선생님에게 원망이 쏟아지게 되기 때문입니다. 저희는 미래 교사로서, 이러한 문제를 프로그래밍적으로 해결해보려고 하였습니다.
학생이 자리에 가지는 만족도는 크게 두가지 일 것입니다. 첫째로 자리의 물리적 위치에 대한 만족 둘째로 해당 자리 주위에 있는 학우들의 분포 입니다.저희는 이중 자리의 물리적 위치에 대한 만족을 최대한 끌어올리는 방향으로 프로그램을 제작하게 되었습니다. 하지만 자리배치에 기본으로 쓰이는 백트래킹 알고리즘으로는 학생 수가 20명만 되어도 계산이 며칠씩 걸리는등, 사실상 프로그램 사용이 불가능할 정도의 계산 복잡도를 보였습니다. 하지만 Branch&Bound 알고리즘을 활용하면 20명의 학생을 대상으로 짧게는 몇초, 길게는 1분으로 시간을 매우 짧게 단축시킬 수 있었습니다.

먼저 사용자 입력값이 필요합니다. intimacy_data.txt 파일과 student_name_data.txt 파일을 작성합니다. 그리고 who's next me.exe 파일을 실행합니다. intimacy_data.txt에는 자리에 대한 학생의 선호도가 들어가게 됩니다. student_name_data.txt에는 출석번호 순, 학생의 이름이 들어가게 됩니다.