[백준] 1931번 회의실 배정 | 파이썬 Python 그리디 알고리즘 구현

2025. 2. 10. 22:38·코딩테스트 준비/문제풀이

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
'코딩테스트 준비/문제풀이' 카테고리의 다른 글
  • [백준] 1850번 최대공약수 파이썬 Python / 유클리드 호제법 풀이
  • [백준] 1012번 유기농 배추 | 파이썬 Python 너비 우선 탐색(BFS)으로 구현
  • [백준] 2178번 미로 탐색 / 파이썬 python 너비 우선 탐색(bfs) 구현
  • [백준] 1753번 최단경로 / 파이썬 python 다익스트라 알고리즘 구현
하이야니
하이야니
또 취준..!
하이야니's 스케치또 취준..!
  • 하이야니
    하이야니's 스케치
    하이야니
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 코딩테스트 준비
        • 알고리즘 개념
        • 문제풀이
      • 파이썬
      • 자바
      • 리눅스
      • C언어
      • 여행
        • 국내
        • 해외
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    백준유클리드호제법
    프로그래머스pccp
    pccp기출문제1번
    유클리드호제법최대공약수
    유클리드호제법파이썬
    pccp기출문제
    태국전자입국
    벨만포드
    프로그래머스파이썬
    벨만포드음수사이클
    프로그래머스코딩테스트
    방콕tdac
    tdac작성방법
    다익스트라
    tdac작성
    백준bfs
    방콕입국신고서작성
    프로그래머스pccp기출문제
    너비우선탐색파이썬
    벨만포드다익스트라
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
하이야니
[백준] 1931번 회의실 배정 | 파이썬 Python 그리디 알고리즘 구현

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.