시간표 편성과 강의실 배치는 대학교나 학원 등에서 매우 중요한 문제입니다. 학생들의 수업 시간을 효율적으로 조정하고, 강의실을 최대한 활용하기 위해서는 그래프 알고리즘을 활용할 수 있습니다. 이번 블로그에서는 그래프 알고리즘을 사용하여 시간표 편성과 강의실 배치를 수행하는 예제를 파이썬으로 작성해보겠습니다.
그래프 알고리즘 이해하기
시간표 편성과 강의실 배치는 그래프 알고리즘의 일종인 색칠 문제로 볼 수 있습니다. 각 과목은 그래프에서 하나의 정점을 나타내고, 서로 겹치지 않게 시간표에 배치되어야 합니다. 이때, 강의실의 수는 정점의 색상과 같고, 이웃하지 않는 강의들은 서로 다른 색상을 가져야 합니다.
파이썬 코드 작성하기
이제 파이썬을 사용하여 시간표 편성과 강의실 배치를 수행하는 코드를 작성해보겠습니다. 예시로 3개의 강의를 편성하고, 2개의 강의실을 배치하는 상황을 가정하겠습니다.
class Lecture:
def __init__(self, name, start_time, end_time):
self.name = name
self.start_time = start_time
self.end_time = end_time
def schedule_lectures(lectures, num_rooms):
schedule = {}
for lecture in lectures:
for room in range(num_rooms):
can_schedule = True
for scheduled_lecture in schedule.get(room, []):
if (scheduled_lecture.start_time <= lecture.start_time <= scheduled_lecture.end_time) or (scheduled_lecture.start_time <= lecture.end_time <= scheduled_lecture.end_time):
can_schedule = False
break
if can_schedule:
if room not in schedule:
schedule[room] = []
schedule[room].append(lecture)
break
return schedule
# Test Code
l1 = Lecture("Math", 9, 10)
l2 = Lecture("Computer Science", 10, 12)
l3 = Lecture("English", 11, 13)
lectures = [l1, l2, l3]
num_rooms = 2
schedule = schedule_lectures(lectures, num_rooms)
for room, scheduled_lectures in schedule.items():
print(f"Room {room + 1}:")
for lecture in scheduled_lectures:
print(f" - {lecture.name}: {lecture.start_time}-{lecture.end_time}")
위의 코드는 Lecture 클래스를 정의하고, schedule_lectures 함수가 입력 받은 강의들을 강의실에 배치하는 로직을 담고 있습니다. 각 강의는 name, start_time, end_time 속성을 가지고 있으며, 이를 활용하여 겹치는 시간대가 없는지 확인합니다. 가능한 강의실을 찾으면 해당 강의를 해당 강의실에 배치하고, 시간표를 업데이트합니다.
실행 결과
위의 코드를 실행하면 아래와 같은 결과가 출력됩니다.
Room 1:
- Math: 9-10
- English: 11-13
Room 2:
- Computer Science: 10-12
결과를 보면, Math는 1번 강의실에, Computer Science는 2번 강의실에, English는 1번 강의실에 배치되었음을 확인할 수 있습니다.
마무리
그래프 알고리즘을 활용하여 시간표 편성과 강의실 배치를 수행하는 예제를 파이썬으로 작성해보았습니다. 이러한 알고리즘은 실제 교육 기관에서 많이 활용되고 있으며, 학생들과 교직원들의 스케줄 관리에 도움이 됩니다. 이를 응용하여 더 복잡한 시간표 편성과 강의실 배치 문제를 해결할 수도 있습니다.