저포함 4명의 팀원들과 3번정도의 연습문제와 기출문제(2019, 2018)를 풀어 대략적인 대회 참여 전략을 세웠고
어느정도 heuristic optimization algorithm(GA, SA)를 학습하였습니다. (실제 대회에서는 사용하지 않음ㅠㅠ)
대회시간은 새벽 02:45 ~ 06:30으로 일개 회사원들에겐 최악의 시간대였습니다.
저흰 새벽1시쯤 뜨끈~뜨끈하고 든~든한 국밥을 먹고 24시 스터디룸에서 대회에 참가하기로 하였습니다.
대회가 시작되었고 문제는 기출과 비슷하게 간단 명료하였습니다. 다만 data set이 기존에 주었던 a~e까지가 아닌
a~f까지 6개의 data set이 있었습니다.
문제를 요약하자면 다음과 같습니다.
[0, B-1]까지의 unique한 book id가 주어지고 [0, L-1]의 unique한 Library가 주어집니다.
각 Library에는 book들이 존재하고 하루동안 scan할 수 있는 book 수가 정해져있습니다.
이 'signup process'는 해당 시간에 최대 한개의 Library만 진행할 수 있습니다.
book$_{i}$을 scan할 때 얻는 score$_{i}$가 제공될 때 점수를 최대화하는 문제입니다.
처음 떠올린 풀이는 현재 $L_{i}$를 선택하였을 때 'signup process'를 끝내고 얻을 수 있는
최대점수의 Library를 택하고 이를 반복하는 naive한 풀이였습니다.
이 풀이로 B는 만점풀이를 받았지만 D,E,F의 점수는 많이 낮았습니다.
(hyperparameter tuning으로 비빈결과 C에서는 다음에 나올 풀이와 점수차이가 많이 나지 않았습니다.)
그 다음 풀이로는 'signup process'당 얻을 수 있는 점수가 가장 큰 $L_{i}$를 택하는 풀이였습니다.
해당 풀이로는 기존의 점수보다 상당히 높은 점수를 얻었습니다.
사실상 이 풀이로 C, E, F (D는 얻을 수 있는 max치의 점수를 얻었다 생각하고 pass하였음)를 비벼
다음과같은 점수를 받았습니다.
등수는 많이 낮았지만 대회동안 상당히 재미있었기 때문에 즐겁게 마무리했던것 같습니다.
대회가 끝나고 상위등수 분들의 풀이는 다양했지만 greedy하게 $L_{i}$를 택하고 순서를 정하였을 때
mcmf로 book을 선택할 때 중복을 제거하여 택하는 솔루션이 흥미로웠습니다.
또한 데이터를 분석하는 능력과 여러 최적화 기법을 알게되어 좋은 계기가 되었던것 같습니다.
댓글 없음:
댓글 쓰기