https://www.acmicpc.net/problem/1931
그리디(greedy), 탐욕 알고리즘은 현재 가장 최선의 선택을 하는 알고리즘이다.
제약 조건에 벗어나지만 않으면 되어서 "항상 최적의 해를 보장하지 않는다" 라는
아주 마음에 안 드는(?) 단점이 있다.
사실 내가 그리디 알고리즘을 별로 선호하지 않는데..
그래도 문제는 풀어야겠지 에효
백준 1931번 회의실 배정 문제는 그리디 알고리즘을 사용하면 된다.
문제

설명
회의를 가장 많이 진행하기 위해서는 회의의 끝나는 시간이 중요 키포인트다.
회의 시작 시간과 끝나는 시간이 같을 수 있다고 문제에 주어졌는데,
예를 들어 (11, 11), (10, 11) 2개의 회의가 있다면 2개 모두 진행이 가능하지만
(11, 11)이 먼저 입력되면 나중에 나온 (10, 11)이 불가능할 수 있다.
따라서 종료 시간이 같으면 시작 시간이 빠른 순서대로 정렬하는 로직을 추가해야 한다.
문제를 푸는 순서는
1. 데이터 입력을 받고 종료 시간 순으로 정렬
2. 종료 시간이 같은 경우에는 시작 시간을 기준으로 다시 한번 정렬
3. 순차적으로 탐색 후 겹치지 않는 회의 시간 선택
코드
import sys
input = sys.stdin.readline
n = int(input())
times = [list(map(int, input().split())) for _ in range(n)]
times.sort(key=lambda x: (x[1], x[0])) # 두번째 값이 같을 경우 첫번째 값을 기준으로 오름차순 정렬
cnt = 0
end_time = -1
for s, e in times:
if end_time <= s:
cnt += 1
end_time = e
print(cnt)
'코딩테스트 준비 > 문제풀이' 카테고리의 다른 글
[백준] 1850번 최대공약수 파이썬 Python / 유클리드 호제법 풀이 (0) | 2025.02.14 |
---|---|
[백준] 1012번 유기농 배추 | 파이썬 Python 너비 우선 탐색(BFS)으로 구현 (0) | 2025.02.11 |
[백준] 2178번 미로 탐색 / 파이썬 python 너비 우선 탐색(bfs) 구현 (0) | 2025.02.10 |
[백준] 1753번 최단경로 / 파이썬 python 다익스트라 알고리즘 구현 (0) | 2025.02.10 |
[백준] 1717번 집합의 표현 / 파이썬 Python (union find) (0) | 2025.02.09 |