문제 특징 및 의도
2023 카카오 호텔 예약 문제는 호텔에 단체 손님들이 예약을 요청할 때, 예약을 승낙 혹은 거절하여 손님에게 알려주고, 손님이 호텔에 도착했을 때 인원수만큼의 비어있는 연속된 객실을 배정해 주는 문제입니다. 점수를 잘 받기 위해서는 적절한 예약 관리와 객실 배정으로 호텔의 이용률을 높이면서 객실 수가 큰 예약을 최대한 거절하지 않는 것이 중요합니다.
객실 수가 큰 예약을 거절해야 하는 경우가 언제 발생하는지를 생각해 보겠습니다. 단순히 호텔이 만실인 경우도 있지만, 이용 중인 객실이 사이에 공실을 끼고 띄엄띄엄 분포해 있는 경우에 빈 객실이 충분한데도 예약을 거절해야 하는 상황이 생깁니다. 이러한 상황은 운영체제의 메모리 단편화(memory fragmentation)와 비슷한 면이 있으며, 메모리 단편화 해결 방법에 대해 고민해 본 적이 있다면 고득점에 유효한 방법을 생각해 내는 데 도움이 될 수 있습니다.
본 문제에서는 2개의 시나리오가 주어집니다. 시나리오 2에서는 객실 수가 큰 예약이 많아지는 성수기가 존재하기 때문에 특별한 전략 없이 차례대로 객실을 배정한다면 이러한 단편화(fragmentation)에 의한 예약 거절이 자주 발생하게 됩니다. 따라서 단편화에 대한 처리가 시나리오 1에 비해 더욱 중요해집니다.
작년에 출제된 게임 매칭 문제는 실생활에 사용되는 Elo 기법을 이용하는 등 최적화 방법을 쉽게 떠올릴 수 있는 편이었습니다. 반면 이번 문제는 최적화 전략을 떠올리는 난이도가 어느 정도 있어서, 고득점을 받기가 작년 문제에 비해 어려웠다고 판단됩니다.
매 날짜마다 API를 사용해 문제를 해결하는 흐름은 보통 다음과 같습니다.
- NewRequests API를 통해 새로운 예약 요청을 확인
- Reply API를 통해 예약 요청에 대한 승낙/거절을 답변
- Simulate API를 통해 오늘 호텔에 도착한 손님들에게 객실을 배정, 그 후 1일 진행
문제 평가 요소
점수는 정확성 점수, 효율성 점수, 페널티 점수로 이루어져 있습니다.
정확성 점수는 호텔 이용률 목표치를 얼마나 달성했는지를 나타내는 점수입니다. 1번 시나리오의 경우 이용률 60%, 2번 시나리오의 경우 이용률 75% 이상을 달성하면 정확성 점수에서 만점을 받을 수 있습니다. 많은 예약이 주어지므로 웬만해서는 큰 어려움 없이 목표치에 근접한 이용률을 달성할 수 있습니다.
효율성 점수는 예약 요청이 발생했을 때 얼마나 빠르게 답변했는지를 나타내는 점수입니다. 예약 발생 즉시 답변하는 경우와 답변 기한까지 최대한 미루다가 답변하는 경우의 차이가 최대 10점까지 생길 수 있으며, 큰 수치는 아니지만 고득점을 노린다면 신경 써야 하는 수치입니다. 답변이 애매한 예약은 적당히 미루다가 답변하고, 거절이나 승낙이 확실한 예약은 빠르게 답변하는 기준을 잘 조율하는 것이 효율성 점수를 챙기기 위해 필요하다고 볼 수 있습니다.
페널티 점수는 예약 거절과 객실 배정 실패마다 받는 점수이며, 점수가 낮을수록 좋습니다. 객실 수가 큰 예약일수록 받는 페널티 점수가 커지기 때문에 이러한 예약을 최대한 거절하지 않는 것이 중요합니다. 예약을 거절한 횟수에 따른 페널티도 존재하기 때문에 객실 수가 적은 예약을 너무 소홀히 해서도 안됩니다. 예약을 승낙했으나 객실 배정에 실패하게 된다면 단순히 예약을 거절한 경우의 약 5배 정도 페널티를 받으므로 이러한 경우는 최대한 없도록 해야 합니다.
정확성 점수는 목표치 달성이 크게 어렵지 않고 효율성 점수의 가중치가 크지 않기 때문에, 페널티 점수를 최대한 줄이는 것, 즉 객실 수가 큰 예약을 최대한 거절하지 않는 것이 총점수를 잘 받기 위해 가장 중요하다고 볼 수 있습니다. 만약 객실 수가 큰 예약을 승낙하는 것에만 치중하여 “객실 수가 적은 예약은 무조건 거절” 등의 방법을 사용한다면 너무 많은 거절 횟수에 의해 페널티 점수가 오히려 커지거나, 정확성 점수를 희생하게 되어 좋은 점수를 받지 못할 수 있으며, 이러한 점수를 잘 조율하는 것이 필요합니다.
문제 접근 방법
최적화 전략을 떠올리는 난이도가 어려웠던 만큼, 응시자별로 여러 가지 다양한 접근 방법을 사용했습니다. 이 중 많은 응시자들이 사용한 가장 단순한 접근 방법과, 상위권 득점자들이 많이 사용한 접근 방법을 소개하겠습니다.
- 예약이 발생하는 순서대로 답변, 가장 낮은 번호의 객실부터 순서대로 객실 배정 (first-fit)
가장 단순한 방법입니다. 예약이 발생하는 즉시 가장 낮은 객실부터 순서대로 확인해 빈 객실이 있다면 객실 배정을 확정시키고, 배정이 불가능하다면 거절합니다. 이 경우, 정확성 점수와 효율성 점수는 잘 받을 수 있지만 페널티 점수가 커지게 되어 고득점을 위해서는 이보다 더 최적화된 전략이 필요합니다.
- 답변 기한을 최대한 활용하며, 객실 수가 큰 예약에 우선순위를 두는 방법
객실 수가 큰 예약을 최대한 거절하지 않는 것이 총점수를 잘 받기 위해 가장 중요하다는 것을 알고, 효율성 점수를 희생하는 대신 최대한 많은 예약을 한꺼번에 고려해 객실 수가 큰 예약을 최대한 많이 승낙하는 방법입니다. 객실 수 외에 머무는 기간 등 우선순위를 두는 기준이 달라질 수 있으며, 답변 기한까지 답변을 미루는 대신 확정된 예약은 빠르게 답변하는 등의 변형이 가능합니다. 많은 응시자들이 가장 단순한 첫 번째 방법과 이 방법을 사용해 문제에 접근했습니다.
- 특정 기준에 따라 거절할 예약을 미리 정해두는 방법
점수 득점에 상대적으로 도움이 되지 않는 예약을 무조건 거절하는 방법입니다. 대표적으로 객실 수가 적은데 머무는 기간이 매우 긴 예약 등이 객실의 단편화를 일으킬 확률이 높으므로 이러한 예약을 잘 골라내 빈 객실이 있더라도 예약을 거절하는 방법입니다.
- 매번 단편화가 가장 작아지도록 객실을 배정하는 방법 (best-fit)
객실의 단편화를 방지하기 위해 객실 배정에도 신경을 쓴 방법입니다. 객실을 배정했을 때 단편화의 크기가 가장 작아지는 객실을 찾아 배정하는 방법입니다. 이를 위해 객실 수와 가장 비슷한 크기로 연속된 객실을 무차별 대입(brute-force)으로 찾아 배정합니다. 예를 들어 배정해야 하는 객실 수가 5일 때 4, 7, 10개 연속으로 빈 객실이 있다면 배정 가능한 위치 중 연속된 크기가 가장 비슷한 7개 연속한 객실에 배정합니다.
- 비슷한 사양의 예약끼리 객실 위치를 몰아 배정하는 방법
객실의 단편화를 방지하기 위한 또 다른 방법입니다. 비슷한 사양의 예약 요청을 최대한 비슷한 위치에 몰아 배정해서 단편화를 피하는 방법입니다. 객실 수, 머무는 기간, 체크아웃 날짜 등을 기준으로 비슷한 사양을 판별할 수 있으며, 단편화 방지 효과를 기대할 수 있습니다. 객실을 비슷한 위치에 모는 방법으로는 층 별로 분리하는 방법, 더 나아가 같은 층 안에서 객실을 일정한 크기로 그룹을 지어 분리하는 방법 등이 있습니다.
문제 요구에 따라 예약 승낙, 거절과 객실 배정 방법 두 가지 분야에서 전략이 다양하게 나올 수 있기 때문에 이 전략의 조합에 따라 다양한 접근 방법과 점수 편차가 있었습니다. 위 방법들을 최고점이 나올 때까지 조합, 변형해 가며 접근한 응시자들이 최상위권 점수를 받을 수 있었습니다.
