[알고리즘 일기] 25. 수강 신청 분석

 

 

문제 25. (2021-05-25)

 

수강 신청 분석

이번 학기 ♣♧대학교의 수업 리스트가 나왔습니다.

 

[(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은 파라미터로 전체 수업 리스트를 받고 가능한 많은 수업을 담은 리스트를 리턴합니다.

 

 

 

❧ 테스트 셋

def course_selection(course_list):
    #Code

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

---

❧ 정답

def course_selection(course_list):
    # 시작 시간 순 정렬
    course_list.sort(key=lambda x:x[0])
    # 종료 시간 순 정렬
    course_list.sort(key=lambda x:x[1])
    course_select = [course_list[0]]
    j = 0
    for i in course_list:
        # (이후 수업의 시작 시간) > (이전 수업의 종료 시간)
        if (i[0] > course_select[j][1]):
            course_select.append(i)
            j += 1
    return course_select


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

 

1️⃣ 리스트 내, 수업 정렬 : 먼저 끝나는 수업으로 정렬하되, 시작 시간이 더 먼저인 수업이 뒤에 있을 수 있으므로 시작 시간 순 정렬을 우선 해준다.

<lambda 함수>

def 함수명(): 과 동일

형식 : 변수명 = lambda 매개변수1, 매개변수2... : 매개변수1, 매개변수2

(이때 : 뒤에는 return할 형태를 적어준다.)

 

2️⃣ 최적 부분 구조 : 첫 번째 선택한 튜플에 맞춰 남은 튜플들 중 최대 개수 조합 선정

탐욕적 선택 속성 :

1) 가장 먼저 시작하는 수업을 고른다.

2) 겹치는 수업이 가장 적은 수업을 고른다.

3) 가장 짧은 수업을 고른다.

4) 가장 먼저 끝나는 수업을 고른다.

출처 입력

→ 남은 리스트에서 가장 먼저 끝나는 수업을 고르는 게 최선의 선택이다.

 

3️⃣ 시간 복잡도

리스트 정렬 : O(n log2n)

반복문 반복 : O(n)

∴ O(n) + O(n log2n) = O(n log2n)

 

 

728x90