그리디 알고리즘 Greedy 파이썬 회의실 배정 BOJ1931 코딩테스트(8)

 

목차

 

서론

지난번엔 그리디 알고리즘 개념과 문제를 풀어보았다. 그리고 예고했던 대로 백준 BOJ1931문제를 풀었다. 처음에는 끝나는 시간 기준으로 어떻게 지지고 볶으면 될 줄 알았으나, 안 됐다. 그냥 천천히 내 풀이로 풀어보면 맞아떨어지지 않았다. 그래서 정답을 보니 아차 싶었다. 과거의 나는 왜 그런 생각을 했을까...

---

 

내 풀이 1 - 오답

내가 풀었던 풀이 과정은 다음과 같다. 오답이니 무시해도 된다. 눈물나지만 공개처형 하는 것에 의의를 뒀다. 여기서 문제였던 점은, 꼭 끝나는 시간이 같거나 다른거에 영향을 안받기 때문이다라고 하면 되려나.모든 것을 고려했어야 됐는데 끝나는시간에 한정해서 경우를 나눈것이 화근이었다고 판단한다.

1. 끝나는 시간 기준으로 정렬한다.

2. 끝나는 시간 같으면 -> 앞에 숫자 더 큰게 이득 -> 앞에 숫자 클 때 answer에 있던 마지막 놈 빼고 해당 회의 넣기.

3. 끝나는 시간 다르다면 -> answer의 마지막 원소의 첫번째 숫자(=시작 시간)와 비교. ->  작으면 넣기, 크면 패스하기.

4. cf. 처음에 비교가 있기 때문에 첫 원소는 넣고 시작하기에, 0번 원소가 아닌 1번부터 for문을 시작한다.

n = 11
l = [
[1, 4]
,[3, 5]
,[0, 6]
,[5, 7]
,[3, 8]
,[5 ,9]
,[6, 10]
,[8 ,11]
,[8 ,12]
,[2 ,13]
,[12, 14]]
answer = []
l = sorted(l,key=lambda x : x[1],reverse = True)
answer.append(l[0])
for i in range(1,n):
    if l[i][1] == answer[-1][1]: #  끝나는 시간 같으면 
        if l[i][0] >= answer[-1][0] : # 앞에숫자 클 때
            x = answer.pop()#마지막 놈 빼고
            answer.append(l[i])#해당 회의 넣기
            
    
    else: #끝나는 시간 다르다면
        if l[i][1] <= answer[-1][0]:  #시작 시간이 작거나 같을때 
            answer.append(l[i]) # 넣기
    print(answer[-1])    

print(answer)

---

정석 풀이

이 문제를 푸는 솔루션은 "현재시간이 t라고할 때 시작 시간이 t이상인 모든 회의 중 가장 먼저 끝나는 회의를 선택하는 것이 좋다." 반례를 찾고 싶다면 지금당장 손해봐도 나중에 이득인 경우는 없을까를 생각하면 좋다고 한다. 이번 문제에서는 (0,6) 을 버리고 (1,4)를 택한 경우 아닐까.

1. 스케줄은 끝나는 시간이 빠른 순으로.

2. 끝나는 시간이 같다면 시작하는 시간이 빠른 순으로 배정해야 된다.

---

내 코드 수정

내 코드를 다시 수정해봤다. 수정한 부분은 크게 1. 정렬 -> 끝 시간이 빠른 순서로 했음. 2. 끝나는 시간 같으면 앞에 숫자 작을때 기존꺼 빼고 새로 넣는걸로 했고 3. 마지막에 넣었던 끝나는 시간보다 시작시간이 느리거나 같은걸 넣었다. 정말 정답은 코앞에있었는 데 왜 나는 반대로 생각했을까.

n = 11
l = [
[1, 4]
,[3, 5]
,[0, 6]
,[5, 7]
,[3, 8]
,[5 ,9]
,[6, 10]
,[8 ,11]
,[8 ,12]
,[2 ,13]
,[12, 14]]
answer = []
l = sorted(l,key=lambda x : x[1])
answer.append(l[0])
for i in range(1,n):

    if l[i][1] == answer[-1][1]: #  끝나는 시간 같으면 
        if l[i][0] <= answer[-1][0] : # 앞에 숫자 작을 때 
            x = answer.pop()#마지막 놈 빼고
            answer.append(l[i])#해당 회의 넣기
            
    if l[i][1] != answer[-1][1]:
        if l[i][0] >= answer[-1][1]:  #끝시간이 작거나 같을때 
            answer.append(l[i]) # 넣기
    print(answer[-1])    

print(answer)

 

---

끝으로

이번 포스팅에서는 그리디 알고리즘의 문제를 풀어보았다. 아마 다음 포스팅에선 이분 탐색과 관련된 것을 하고자 한다. 그리디는 다음 사이클 때 돌아올 예정임. 문제풀이 사이클이 궁금하다면 여기로.