[코딩 테스트] 6일차.

회의실 배정(그리디)

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

처음에는 문제를 이분탐색으로 접근하였다. n(1<=n<=100,000)이 주어진다. 이므로 이중 반복문 사용하면 시간초과도가 뜰게 자명했기 떄문이다. 내가 처음에 푼 코드는 다음과 같다.

N = int(input())

conference = [list(map(int, input().split())) for _ in range(N)]
start = end = []
for i in range(len(conference)):
    start.append(conference[i][0])
    end.append(conference[i][1])

#conference.sort()
conference.sort(key = lambda x: (x[1], x[0]))
#람다식 사용해서 key에서 2번째 값을 기준으로 오름차순 정렬
#print(conference)
lt = min(start)
rt = max(end)
#print(lt, rt)

while True:
    tmp = conference[0]
    cnt = 1
    mid = (lt + rt) // 2
    # print(mid)
    # print(f'tmp:{tmp}')
    # print(f's:conference {conference}')
    for x, y in conference:
        #print(x, y)
        if tmp[1] <= x:
            cnt += 1
            tmp = x, y
        elif tmp[0] <= x and tmp[1] >= y:
            tmp = x, y
        #print(f'cnt:{cnt}')
    #print(f'e:conference {conference}')
    if cnt < mid:
        rt = mid - 1
    else:
        res = cnt
        lt = mid + 1
    if lt > rt:
        break

print(res)
# cnt = 0
# et = 0
# for x, y in conference:
#     if x >= et:
#         cnt += 1
#         et = y
# print(cnt)
'''
5
1 4
2 3
3 5
4 6
5 7
'''

Greedy Algorithm:
문제를 풀어나가는 과정(단계)에서 이 단계에서 가장 좋은게 무엇인지를 판별해서 가장 좋은 것을 선택함. "정렬"하고 나서 차례 차례 선택해 나는게 그리디 알고리즘의 문제접근 방법!

cnt = 0
et = 0
for x, y in conference:
    if x >= et:
        cnt += 1
        et = y
print(cnt)

(x, y)로 튜플로 리스트 값이 주어져 있을 때, 만약 x가 아닌 y값을 기준으로 오름차순 정렬을 하고 싶다면,
람다식을 써야한다.

conference.sort(key = lambda x: (x[1], x[0]))

이 코드식은 외워야할 것 같다.(유용하다고 강사님께서 말씀하셨다.)

결정 알고리즘과 그리디 알고리즘의 유형을 어떻게 구분해야할지 아직 모르겠다.
좀더 문제를 풀면서 접근해봐야겠다.

출처:https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8/unit/26936