그리디 알고리즘 1

문제에 앞서 Greedy(탐욕법)가 무엇인지 알아보겠습니다. 각 단계마다 지금 당장 가장 좋은 방법만을 선택하는 해결 방법입니다. 많은 경우 최적해를 찾지 못하고 적용될 수 있는 경우가 두 가지로 제한됩니다

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 경우
2. 시간이나 공간적 제약으로 최적해 대신 근사해를 찾아서 해결하는 경우

접근 방법

1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다. 작은 입력을 손으로 풀어본다.
3. 다음 두 속성이 적용되는지 확인해본다.
4. 탐욕적 성택 속성 : 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재하는가
5. 최적 부분 구조 : 각 단계에서 항상 최적의 선택만을 했을 때, 전체 최적해를 구할 수 있는가

 

 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

 

▣ 입력설명

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정 보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

 

import sys
sys.stdin=open("input.txt", "rt")

n=int(input())
meeting=[]
for i in range(n):
    s, e=map(int, input().split())
    meeting.append((s, e))
meeting.sort(key=lambda x :(x[1], x[0]))

et=0
cnt=0
for s, e in meeting:
    if s>=et:
        et=e
        cnt+=1
print(cnt)

 회의의 수 n을 input으로 입력받고, s(시작시간), e(회의끝나는 시간)을 meeting이라는 빈 list에 입력하겠습니다.

이 때 회의를 제일 많이해야 하기 때문에, 회의가 끝나는 시간(e)을 기준으로 오름차순으로 정렬을 해야 합니다. 

 meeting.sort로 하게 된다면 s를 기준으로 오름차 정렬이 되기 때문에 lambda 함수를 이용하여 e를 기준으로 정리해보겠습니다.

 

 lambda 함수의 형식은 lambda (매개변수) = 매개변수를 이용한 return 값 이 나오는 형식입니다.

https://velog.io/@aonee/Python-%EC%A0%95%EB%A0%AC-sort-sorted-reverse

 key 인자에 함수를 넘겨주면 x[1], x[0]의 순서대로 정렬하여 List가 완성이 됩니다. 이제 회의를 몇 번 할 수있는지 확인해야겠죠.

 et(endtime)과 cnt를 0으로 초기화 시킨뒤 s, e로 반복문을 실행합니다.

시작시간(s)이 et보다 크게되면 et에 끝나는 시간을 저장하고 cnt를 하도록 반복합니다.

먼저 (2, 3)이 들어오게 되면 첫 번째이기 때문에 et에 저장이 됩니다. 그리고 반복하죠

(1, 4)가 들어오게 되는데 이 때 1(s)가 4(et)보다 작기 때문에 저장이 되지않고, 다음 반복문으로 넘어갑니다.

 그렇게 튜플형식의 리스트를 모두 반복한 뒤 출력하게 되면 답이 나올 것입니다.