[백준][그리디] 회의실 배정

오늘의 학습 키워드

정렬, 그리디 알고리즘

 

오늘의 회고

🌱 오늘의 문제

https://www.acmicpc.net/problem/1931

 

10만 이하의 정수 n이 입력으로 주어지고, 이어서 n개의 회의 시간(시작 시간, 종료 시간)이 주어진다.

하나의 회의실에 대해 최대 몇 개의 회의가 진행될 수 있는지 찾는 문제이다.

 

이 때 주의할 점은 아래와 같다.

1. 회의 시작 시간과 종료 시간이 동일할 수 있다 → 예: (1, 1) 가능

2. 이전 회의 종료 시간에 다음 회의가 시작할 수 있다. → 예: (1, 3), (3, 5) 가능

 

 

🌱 나의 시도

최종적으로 정렬 + 그리디 알고리즘으로 이 문제를 해결하였다.

 

이 문제를 처음 보았을 때 그리디 알고리즘으로 시도해보고, 잡히지 않는 반례가 있을 경우 그래프 탐색으로 접근하고자 했다.

또한 그리디 알고리즘에서는 아래 세 가지 형태로 정렬을 하여 형태를 살펴보았다.

1. 시작 시간 기준 정렬

2. 회의 시간 간격 기준 정렬

3. 종료 시간 기준 정렬

 

n = int(input())
meetings = [list(map(int, input().split())) for _ in range(n)]

# 시작 시간 기준 정렬
res1 = sorted(meetings)
print("시작 시간 기준:")
display(res1)
print()

res2 = sorted(meetings, key=lambda x: (x[1]-x[0]))
print("회의 시간 간격 기준:")
display(res2)
print()

res3 = sorted(meetings, key=lambda x: (x[1], x[0]))
print("종료 시간 기준:")
display(res3)
print()

""" 실행 결과]
[입력]
 11
 1 4
 3 5
 0 6
 5 7
 3 8
 5 9
 6 10
 8 11
 8 12
 2 13
 12 14
 
 [출력]
시작 시간 기준:
[[0, 6],
 [1, 4],
 [2, 13],
 [3, 5],
 [3, 8],
 [5, 7],
 [5, 9],
 [6, 10],
 [8, 11],
 [8, 12],
 [12, 14]]

회의 시간 간격 기준:
[[3, 5],
 [5, 7],
 [12, 14],
 [1, 4],
 [8, 11],
 [5, 9],
 [6, 10],
 [8, 12],
 [3, 8],
 [0, 6],
 [2, 13]]

종료 시간 기준:
[[1, 4],
 [3, 5],
 [0, 6],
 [5, 7],
 [3, 8],
 [5, 9],
 [6, 10],
 [8, 11],
 [8, 12],
 [2, 13],
 [12, 14]]
"""

 

 

그리디 접근 방식을 고려하였을 때, 배열을 순차적으로 탐색하면서 결과를 찾는 것이 좋다고 생각하였다.

그리고 정렬 결과를 확인해보았을 때 "종료 시간"을 기준으로 정렬한 결과가 이에 가장 적합하였다.

 

현재 시점에서 가장 빠르게 종료된 회의를 찾고, 그 값을 기준으로 이후에 시작된 가장 빠르게 종료되는 회의를 찾는 방식이다.

 

이러한 접근 방식을 통해 아래와 같은 코드를 구현하였다.

 

n = int(input())
meetings = [list(map(int, input().split())) for _ in range(n)]

# 종료시간 기준 정렬
meetings = sorted(meetings, key=lambda x: (x[1], x[0]))

answer, time = 0, -1
for st, en in meetings:
    if st >= time: 
        time = en
        answer += 1
print(answer)

 

 

 

🌱 새롭게 알게 된 점

그리디 알고리즘의 원리는 단순하게 느껴졌는데, 실제 적용을 위해서는 다양한 부분을 고려해주어야 한다는 것을 알게 되었다.

이 문제를 통해 주어진 조건 내에서 알고리즘의 적용이나 값의 처리를 어떻게 해주어야 할 지 설계하는 역량을 키울 수 있었다.

 

 

오늘의 후기

이 문제는 다양한 시도를 해 본 것에 비해, 왜 이게 잘 동작하는 지에 대한 검증은 잘 되지 않은 것 같다.

이 문제가 왜 그리디하게 접근했을 때 잘 동작하는지, 다른 반례가 더 있지는 않은지 조금 찝찝하다.

제대로 된 설계 없이, 다양한 시도 끝에 괜찮아 보이는 것들로 조합하다 보니 이런 결과를 보인 듯 하다.

 

그래프 탐색으로 이 문제를 한 번 더 시도해보면서, 왜 이 문제가 그리디로도 충분했는지 한 번 더 고민해보는 시간을 가져야겠다.