인프런 커뮤니티 질문&답변

네, 답변 감사합니다.

별개의 질문이지만 나중에 혹시 알고리즘 문제 해법들중 O(n) 시간복잡도도 추가하실의향은 없으신가요? 

안녕하세요^^

사실 그리디 알고리즘의 정당성을 증명하기란 정말 어려운 것 같습니다.  

회의실 배정문제를 증명하자면

주어진 입력의 n개의 회의들 중 종료시간이 가장 빠른 회의를 "S_min" 이라고 하겠습니다.

"종료시간이 가장 빠른 회의(S_min)를 포함하는 최적해가 반드시 존재한다" 를 증명하면 됩니다.

만약 최적해중에 S_min를 포함하지 않는 답이 있다고 생각해보세요. 이 답은 서로 겹치지 않는 회의의 목록인데, 이 목록에서 첫 번째로 개최되는 회의 대신 S_min으로 바꾸어도 답이 된다는 것을 알 수 있습니다. 즉 항상 S_min을 포함하는 최적해는 존재합니다. 이와 같은 증명은 우리가 매 단계마다 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 가능하다는 것을 알 수 있습니다.