문제 설명
회의실 배정 문제는 여러 개의 회의가 주어진 경우, 각 회의의 시작 시간과 종료 시간을 바탕으로 회의실을 최적으로 배정하는 문제입니다. 주어진 회의가 겹치는 경우는 회의실을 추가로 배정해야 하므로, 이러한 경우를 피하면서 최대한 많은 회의를 진행할 수 있도록 배정하는 것이 목표입니다.
문제 정의
주어진 회의의 시작 시간과 종료 시간을 리스트 형태로 입력받아, 회의실 배정을 통해 몇 개의 회의를 동시에 진행할 수 있는지를 계산하세요.
입력 형식
[[시작시간1, 종료시간1], [시작시간2, 종료시간2], ...]
출력 형식
가능한 최대 회의 수
예시
입력: [[1, 3], [2, 4], [3, 5], [6, 8]]
출력: 3
문제 풀이 과정
이 문제는 그리디 알고리즘을 사용하여 해결할 수 있습니다. 각 회의의 종료 시간을 기준으로 회의를 정렬한 후, 가장 먼저 끝나는 회의를 선택하고 그 다음 회의가 끝나는 시간과 겹치지 않도록 선택하는 방식입니다.
1단계: 데이터 정리
먼저 주어진 회의 리스트를 종료 시간을 기준으로 정렬합니다. 이렇게 함으로써 가장 적게 자원을 소모하면서 회의를 진행할 수 있습니다.
2단계: 회의 참석 가능한지 판단
정렬된 회의 리스트에서 첫 번째 회의를 선택하고, 다음 회의가 이 회의의 종료 시간보다 크거나 같을 경우 그 회의를 선택합니다. 이러한 과정을 반복하여 최대한 많은 회의를 선택합니다.
3단계: 구현
이제 위의 과정을 바탕으로 파이썬 코드를 구현해보겠습니다.
python
def max_conferences(conferences):
# 회의 리스트를 종료 시간을 기준으로 정렬
conferences.sort(key=lambda x: x[1])
# 첫 번째 회의 선택
count = 1
last_end_time = conferences[0][1]
# 나머지 회의들에 대해 반복
for i in range(1, len(conferences)):
if conferences[i][0] >= last_end_time: # 시작 시간이 마지막 회의 종료 시간보다 크거나 같으면
count += 1
last_end_time = conferences[i][1] # 마지막 회의 종료 시간 업데이트
return count
# 예시 입력
meetings = [[1, 3], [2, 4], [3, 5], [6, 8]]
result = max_conferences(meetings)
print("최대 회의 수:", result)
4단계: 코드 설명
코드 설명
- 정렬: 첫 번째 줄 where `conferences.sort(key=lambda x: x[1])`는 각 회의 끝나는 시간 기준으로 리스트를 정렬합니다.
- 회의 선택: 이후 반복문을 통해 각 회의가 마지막으로 선택된 회의가 끝난 후 시작되는지 확인하여 선택합니다.
- 결과 리턴: 최종적으로 선택된 회의 수를 리턴합니다.
5단계: 복잡도 분석
이 알고리즘의 시간 복잡도는 정렬에 O(n log n), 회의를 선택하는 데 O(n)이므로 총 O(n log n)의 복잡도를 가집니다. 공간 복잡도는 O(1)입니다.
6단계: 추가 연습 문제
이 문제를 통해 그리디 알고리즘의 기본 개념을 익힌 후, 다양한 추가 연습 문제를 풀어 보면 좋습니다. 예를 들어:
- 회의의 시작 시간과 종료 시간이 임의의 범위에서 주어질 때, 가장 적은 회의실 수로 모든 회의를 진행할 수 있는가?
- 회의실을 예약하는 시스템을 구현하여 사용자가 직접 회의를 추가하고 확인할 수 있는 프로그램을 만들어보세요.
결론
이번 강좌에서 “회의실 배정하기” 문제를 통해 그리디 알고리즘을 적용한 문제를 해결하는 방법에 대해 알아보았습니다. 이를 바탕으로 알고리즘 문제 해결 능력을 기르는 데 많은 도움이 되기를 바랍니다. 다음 강좌에서는 더욱 다양한 알고리즘 문제를 다뤄보겠습니다.