[알고리즘] Greedy Algorithm : 수강신청

실습설명

이번 학기 코드잇 대학교의 수업 리스트가 나왔습니다.

[(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 6), (13, 16), (9, 11), (1, 8)]

리스트에 담겨있는 튜플들은 각각 하나의 수업을 나타냅니다. 각 튜플의 0번째 항목은 해당 수업의 시작교시, 그리고 1번 항목은 해당 수업이 끝나는 교시입니다. 예를 들어서 0번 인덱스에 있는 튜플값은 (4,7)이니까 해당 수업은 4교시에 시작해서 7교시에 끝나는 거죠.

 

(2,5)를 듣는다고 가정합시다. (4,7)수업은 (2,5)가 끝나기 전에 시작하기 때문에, 두 수업은 같이 들을 수 없습니다.반면, 수업(1,3)과 (4,7)은 시간이 겹치지 않기 때문에 동시에 들을 수 있습니다.

 

(단, (2,5), (5,7)과 같이 5 교시에 끝나는 수업과 5교시에 시작하는 수업은 서로 같이 듣지 못한다고 가정합니다.)

열정이 불타오르는 신입생 지웅이는 최대한 많은 수업을 들을 수 있는 수업 조합을 찾아주는 함수 course_selection 함수를작성하려고 합니다.

course_selection은 파라미터로 전체수업 리스트를 받고 가능한 많은 수업을 담은 리스트를 리턴합니다.

 

힌트1

Brute Force로 가능한 모든 조합들을 비교하는 방법도 있습니다.하지만 너무 오래 걸리겠죠. 이 문제에는 최적 부분 구조와 탐욕적 선택 속성이 있기 때문에, Greedy Algorithm 방식으로 효율적이면서도 정확한 함수를 구현할 수 있습니다.

 

이문제에서 매단계마다 가장 좋아보이는 선택은 무엇일까요?

 

힌트2

수강 신청 분석에서 보았듯, 가장 먼저 끝나는 수업을 선택하는 것이 최적의 선택입니다.

course_list를 가장 먼저 끝나는 순으로 정렬해야겠죠?

 

힌트3

sorted 함수를 사용하면 정렬을 할 수 있는데 어떻게 해야 우리가원하는 기준으로 정렬 할 수 있을까요?

 

힌트4

# 먼저 시작하는 순으로 정렬
sorted_list = sorted(course_list, key=lambda x: x[0])

# 먼저 끝나는 순으로 정렬
sorted_list = sorted(course_list, key=lambda x: x[1])

# 짧은 순으로 정렬
sorted_list = sorted(course_list, key=lambda x: x[1] - x[0])

sorted 함수에 key파라미터를 이용하면 원하는 기준으로 리스트를 정렬할 수 있습니다.

 

힌트5

이미 고른 수업이 끝나는 시간이 다른 수업이 시작하는 시간보다 늦으면, 두 수업은 겹친다고 볼 수 있습니다.

 

 

 

답안

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)]))