프로젝트를 진행하면서 엄청 문제가 있던 부분이 있다.
그룹의 인원을 근무에 매칭시키는 핵심 알고리즘을 만드는 중이었는데
- 근무 비율로 sort해서 가장 근무 비율이 낮은 인원부터 근무를 세우는 것이
- 해당 인원이 가장 적게 섰던 근무에 배치한다
그랬더니 근무 인원이 비교적 적었던 CCTV근무에 모든 인원이 들어가고.. 뭐 여기까진 문제가 없었다.
내가 간과한 사실은, 그룹별로 평균 근무 비율이 같지 않다는 점이었다.
본부중대는 탄약고 근무를 들어가지 않습니다! 대신 상황병 근무를 맡죠.
매일 가장 많은 근무자를 필요로 하는 탄약고 근무, 하지만 본부중대는 여러여러 이유로 상황병 근무를 완전히 도맡게 되었는데...
그래서 그룹별로 평균 근무 비율이 완전히 달랐다.
뭐, 그건 괜찮다. 그만큼 비교적 쉽고 몸이 편한 근무를 맡을테니.
근데 알고리즘이랑 섞이니 문제가 발생한다.
- 근무비율이 제일 낮은 본부중대 먼저!
- 하루에 딱 두자리 있어서 가장 비율이 낮은 CCTV근무!
아니.. CCTV근무는 하루에 딱 두자리 있어서, 모든 인원이 전역할 때까지 몇 번 못서고 전역하는 근무이다.
그렇게 대부분의 CCTV근무를 본부중대가 독점하게 된다.
이건 말이 안된다.
거기에, 본부중대가 CCTV를 몰아섰기에, 본부중대가 담당해야하는 다른 근무들이 인원이 비어서 기어코 인원이 빈 근무가 생기가 되었다.
본부중대 인원이 CCTV를 독식하는 것도 문제지만,
제일 큰 문제는 근무는 절대로 비어서는 안된다는 점이다.
어떻게 문제를 해결하지?
인원이 근무를 찾아가는게 아니라, 근무가 인원을 찾아가게 해야하나?
그럼 인원들의 근무비율은 어떻게 찾아가지??
하다가 여기에 적절한 알고리즘 문제를 찾아갔다.
내가 부족한 것은 이를 해결할 알고리즘을 몰랐었기 때문이라고 생각했고, 언젠간 봐뒀던 열혈강호 문제가 생각났다.
티어가 높아서(무려 플레티넘) 손 댈 생각도 못했던 문제였지만, 비슷한 문제들을 해결하면 풀어낼 수 있을 것이라 생각했다.
핵심 알고리즘은 이분 매칭이었고, 한가지를 풀어보니, 다양한 응용 문제들을 풀 수 있었다.
많이 풀긴 했다.... ㅋㅋㅋ
이분 매칭은 최대 인원에게 일을 매칭시킬때 사용하는 알고리즘이고, 지금 상황에서 가장 필요한 알고리즘이다.
// userList는 해당 날짜에 근무가 가능한 인원의 목록이다. (전날 근무가 없는 사람)
// 근무 비율이 낮은 인원부터..
userList.sort(compareWorkRate);
// 오늘 필요한 근무의 목록을 받아서..
const todayWork = getTodayWork(day);
// 매칭에 필요한 인원의 수를 센 뒤,
const todayWorkUserNumber = getWorkUserNumber(todayWork)
for(let i = 0; i < userList.length; i++){
// matchWork 내에서는 이분매칭으로 재귀적 호출
if(matchWork(userList[i], todayWork, day)) {
todayWorkUserNumber--;
}
if(todayWorkUserNumber == 0) break;
}이 알고리즘을 활용해서, 두마리 문제를 전부 해결할 수 있었다.
이분매칭으로 해결하되, 인원이 꽉 차면 더이상의 매칭은 불필요했다.
이를 조건으로 만드니, 가장 근무가 적은 인원부터 근무를 채워지고, CCTV처럼 공용이지만 인원은 적은 근무도 나눠가질 수 있었다.
알고리즘은 역시 재밌다.
지난번 포스팅이었던 N-Rook문제를 풀어보길 정말 잘했다는 생각이 드는 하루다.
