2023 카카오 신입 공채 코딩 테스트, 메모리 단편화 개념 적용한 호텔 예약 문제 해설

2023 카카오 신입 공채 2차 코딩 테스트의 '호텔 예약' 문제는 단체 손님의 예약 승낙 및 객실 배정 과정에서 메모리 단편화(memory fragmentation) 개념을 적용해 최적화하는 문제다. 단순한 예약 처리가 아닌, 빈 객실이 충분함에도 연속된 공간 부족으로 예약을 거절해야 하는 상황을 해결하는 전략이 요구된다.

평가 요소와 전략

점수는 정확성, 효율성, 페널티로 구성된다. 정확성은 이용률 목표(시나리오 1: 60%, 2: 75%) 달성 여부이며, 효율성은 답변 속도에 따라 최대 10점 차이가 난다. 가장 중요한 것은 페널티 최소화인데, 특히 객실 수가 큰 예약의 거절이나 배정 실패 시 페널티가 크므로 이를 피하는 것이 총점 상승의 관건이다.

주요 접근 방법

응시자들은 다음과 같은 다양한 전략을 조합해 문제를 해결했다.

• First-fit: 가장 낮은 번호의 빈 객실부터 순차적으로 배정하는 가장 단순한 방법.
• 우선순위 기반 답변: 답변 기한을 활용해 객실 수가 큰 예약을 우선적으로 고려하고, 확실한 예약만 빠르게 답변하는 방식.
• Best-fit: 배정 후 남는 빈 공간(단편화)이 가장 작아지도록 객실 크기와 유사한 연속 공간을 찾아 배정.
• 그룹화: 비슷한 사양(객실 수, 기간 등)의 예약을 특정 층이나 구역에 몰아 배정해 단편화를 방지.