작성자: 김동희

• 교수님 질문

byebye나의지난날

시나리오: 도서관 예약 시스템

백남학술정보관(도서관명)은 열람실 좌석 예약 시스템을 개선하고자 한다. 학생들은 빈 좌석을 검색하고 예약하거나 예약을 취소할 수 있다. 또한 좌석은 시간순으로 관리되며, 예약이 끝난 좌석은 자동으로 정리되어야 한다.

논의주제

• 빈 좌석을 빠르게 찾기 위해 어떤 자료구조가 유리할까?
• 시간 순서를 유지하면서 삽입/삭제가 빈번한 데이터를 어떻게 관리할까?
• 배열, 해시테이블, 연결리스트, 스택, 큐 중 어떤 자료구조가 효율적일까?

목표

1. 사용자가 원하는 시간대에 열람실을 빠르게 검색할 수 있어야 함

   ⇒ 해시테이블이 적절!

• 해시테이블은 키-값(key-value) 쌍으로 데이터를 저장하며, 키를 통해 직접 접근 가능
  • 시간복잡도 O(1)로 예약 여부 확인 가능
• ex: seats[”18”] → 좌석 18번의 예약 정보 바로 확인

2. 시간 순서에 따라 정렬된 상태에서 삽입과 삭제가 빈번하게 이루어질 수 있어야 함

⇒ 시간 순 관리는 큐, 삽입/삭제 관리는 연결리스트가 적절

• 연결리스트는 데이터가 포인터로 연결되어 있어 삽입/삭제가 용이함
  • 시간복잡도 O(1)로 삽입/삭제 가능