C++ 코딩테스트 강좌, 회의실 배정하기

회의실 배정하기

문제 설명

N개의 회의가 진행되어야 하고, 각각의 회의는 시작 시간과 끝 시간을 가집니다.
이 회의들 중에서 최대한 많은 회의를 진행하기 위해 회의실을 어떻게 배정할 것인가?
즉, 회의들이 겹치지 않도록 회의실을 배정하는 알고리즘을 구현해야 합니다.

입력: 각 회의의 시작 시간과 끝 시간을 가진 리스트가 주어진다.
예를 들어, [(0, 30), (5, 10), (15, 20)]과 같은 형태의 리스트가 있을 수 있다.

출력: 최대 배정 가능한 회의 수를 출력한다.

문제 접근 방법

이 문제는 대표적인 그리디 알고리즘 문제입니다.
회의의 종료 시간을 기준으로 정렬한 후,
가장 빨리 끝나는 회의부터 진행하고 다음 회의를 선택하는 방식을 사용합니다.

이렇게 하면 회의가 겹치지 않도록 최적의 회의 배정을 할 수 있습니다.
각 회의의 시작 시간이 이전 회의의 끝 시간보다 크거나 같은 경우에만 회의를 진행할 수 있습니다.

단계별 해결 과정

모든 회의 정보를 입력받는다.
회의를 종료 시간 기준으로 정렬한다.
최대 회의 수를 세기 위해 변수를 초기화한다.
회의를 순회하면서 가능하면 회의를 추가한다.
총 배정 가능한 회의 수를 출력한다.

C++ 코드 구현

#include 
#include 
#include 

using namespace std;

// 회의 정보를 위한 구조체
struct Meeting {
    int start;
    int end;
};

// 회의 종료 시간을 기준으로 정렬하는 함수
bool compare(Meeting m1, Meeting m2) {
    return m1.end < m2.end;
}

// 회의실 배정 함수
int maxMeetings(vector &meetings) {
    // 종료 시간 기준으로 정렬
    sort(meetings.begin(), meetings.end(), compare);
    
    int count = 0;
    int lastEndTime = 0;

    for (const auto &meeting : meetings) {
        if (meeting.start >= lastEndTime) {
            // 회의 진행
            count++;
            lastEndTime = meeting.end; // 마지막 종료 시간 업데이트
        }
    }

    return count;
}

int main() {
    vector meetings = {{0, 30}, {5, 10}, {15, 20}};
    
    int result = maxMeetings(meetings);
    
    cout << "최대 배정 가능한 회의 수: " << result << endl;
    return 0;
}

각 단계에 대한 설명

첫 번째로, 구조체를 사용하여 회의의 시작 시간과 종료 시간을 저장합니다.
그리디 알고리즘에서 중요한 점은 각 회의를 종료 시간 순으로 정렬해야 한다는 것입니다.

정렬 후, 반복문을 통해 각 회의를 확인합니다.
만약 이전 회의의 종료 시간보다 현재 회의의 시작 시간이 크거나 같다면,
이 회의를 진행할 수 있으므로 카운트를 증가시키고 마지막 종료 시간을 업데이트합니다.

모든 회의를 확인한 이후 최종적으로 카운트한 값이 최대 배정 가능한 회의 수가 됩니다.

테스트 케이스

위 코드를 테스트하기 위해 몇 가지 테스트 케이스를 만들어 볼 수 있습니다.

vector test1 = {{1, 3}, {2, 5}, {4, 6}}; // 예상 결과: 2
vector test2 = {{1, 10}, {2, 3}, {4, 5}, {6, 8}}; // 예상 결과: 3
vector test3 = {{1, 2}, {3, 4}, {5, 6}}; // 예상 결과: 3

각 테스트 케이스를 실행하여 기대하는 결과와 비교하여
코드가 올바르게 작동하는지 검증할 수 있습니다.

결론

이번 강좌에서는 C++를 이용한 회의실 배정하기 문제를 해결하는 방법을 알아보았습니다.
그리디 알고리즘이 어떻게 최적의 해법을 제공하는지를 이해하고,
여러 회의의 시작과 종료 시간을 고려하여 최대한 많은 회의를 배정할 수 있음을 보여주었습니다.

여러분도 이 알고리즘을 이해하고 응용하여 더 복잡한 문제를 해결해 보시기 바랍니다.
다양한 알고리즘 문제를 푸는 습관이 여러분의 코딩 실력을 향상시킬 것입니다.