Algorithm(알고리즘)/Greedy Algorithm
4) 수업 겹치지 않게 수강하기
반응형
4) 수업 겹치지 않게 수강하기
[(1, 2), (3, 4), (0, 6), (5, 7)]
튜플 앞 : 수업 시작시간
튜플 뒤 : 수업 종료시간
(0,6) 을 먼저 수강하기로 하면 다른 수업은 못 듣는다
풀이 (1)
def course_selection(course_list):
course_list.sort()
subject = [course_list[0]]
for i in range(1, len(course_list)):
if subject[0][1] > course_list[i][1]:
subject = [course_list[i]]
end = subject[0][1]
for i in course_list[2:]:
if end < i[0]:
subject.append(i)
end = subject[-1][1]
return subject
# 테스트
print(course_selection([(6, 10), (2, 3), (4, 5), (1, 7), (6, 8), (9, 10)]))
print(course_selection([(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]))
print(course_selection([(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 5), (13, 16), (9, 11), (1, 8)]))
# 결과
[(2, 3), (4, 5), (6, 8), (9, 10)]
[(1, 2), (3, 4), (5, 7), (8, 9)]
[(1, 3), (4, 7), (8, 10), (13, 16)]
풀이 (2)
def course_selection(course_list):
# 수업을 끝나는 순서로 정렬한다
sorted_list = sorted(course_list, key=lambda x: x[1])
# 가장 먼저 끝나는 수업은 무조건 듣는다
my_selection = [sorted_list[0]]
# 이미 선택한 수업과 안 겹치는 수업 중 가장 빨리 끝나는 수업을 고른다
for course in sorted_list:
# 마지막 수업이 끝나기 전에 새 수업이 시작하면 겹친다
if course[0] > my_selection[-1][1]:
my_selection.append(course)
return my_selection
# 테스트
print(course_selection([(6, 10), (2, 3), (4, 5), (1, 7), (6, 8), (9, 10)]))
print(course_selection([(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]))
print(course_selection([(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 5), (13, 16), (9, 11), (1, 8)]))
# 결과
[(2, 3), (4, 5), (6, 8), (9, 10)]
[(1, 2), (3, 4), (5, 7), (8, 9)]
[(1, 3), (4, 7), (8, 10), (13, 16)]
풀이 (1)
풀이 (2)반응형
'Algorithm(알고리즘) > Greedy Algorithm' 카테고리의 다른 글
3) 최소 지각 벌금 문제 (0) | 2021.05.16 |
---|---|
2) 세 사람의 카드게임에서 한장씩 뽑아 가장 큰 곱 출력 함수 (0) | 2021.05.16 |
1) 최소 동전으로 거슬러주기(greedy algorithm) (0) | 2021.05.16 |
댓글