오늘은 백준 1931번 문제인 회의실 배정 문제를 풀어보았습니다. 회의실 배정문제는 대표적인 ‘그리디 알고리즘’ 문제입니다.
그리디 알고리즘이 무엇인지 간략하게 설명드리자면, 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 따라서 항상 최선의 답을 가져다 주지는 않습니다.
그리디 알고리즘을 사용하는 대표적인 문제로는
먼저, 활동 선택 문제의 예시로는 각 수업마다 시작시간과 끝나는 시간이 잇을 때 하루에 가장 많은 수업을 할 수 있는 경우를 고르는 것입니다. 하루에 가장 많은 수업을 하기 위해서는 짧은 수업들을 여러개 선택하면 됩니다. 즉, 각 단계에서 가장 빨리 끝나는 수업을 선택하면 됩니다.
이렇듯, 미래를 생각하지 않고 각 단계에서 최선인 짧은 수업을 선택하는 것이 바로 그리디 알고리즘을 사용하는 것입니다.
그리고 분할 가능 배낭문제의 예시로는 배낭에 담은 물건들의 가치 총합이 가장 최대가 되도록 물건을 담는 것입니다. 단, 물건이 배낭에 담기에 너무 무거울 경우 물건을 나누어서 배낭에 담을 수 있는 경우입니다. 이럴 때는 각 단계에서 무게 대비 가치가 높은 것들을 먼저 넣는 것이 좋습니다. 따라서 이 경우도 그리디 알고리즘을 사용하는 문제에 해당합니다.
회의실 문제이 경우 활동 선택문제의 일종이라고 볼 수 있습니다. 각 회의가 겹치지 않으면서 회의실을 사용할 수 있는 최대 회의 개수를 찾는 것이기 때문에 각 단계에서 가장 빨리 끝나는 회의들을 찾으면 됩니다.
즉, 맨 처음에는 ‘가장 빨리 시작’하고 가장 빨리 끝나는 회의를 찾아야합니다. 그렇기 때문에 시작 시간을 기준으로 정렬합니다.
그다음에는 ‘가장 빨리 끝나는’ 회의를 찾아야합니다. 따라서 앞에서 정렬한 결과를 끝나는 시간을 기준으로 정렬합니다.
그리고 가장 빨리 시작하고 가장 빨리 끝나는 회의를 제일 먼저 선택하고, 선택한 회의의 끝나는 시간보다 끝나는 시간으로 큰 숫자를 갖는(늦게 끝나는) 회의를 정렬한 결과에서 찾습니다. 찾은 회의의 끝나는 시간을 기준으로 반복하여 끝나는 시간으로 큰 숫자를 갖는 회의를 찾으면 하루에 가장 많은 회의를 할 경우에 회의의 집합을 찾을 수 있습니다.
말로만 설명하면 어려우니 코드로 설명드리자면 다음과 같습니다.