[백준] 1931. 회의실 배정 (자바스크립트/js/javascript/node.js/정렬/그리디 알고리즘/탐욕적 알고리즘)

문제를 풀기 위한 아이디어 시간 제한은 2초이므로 대략 2억번의 연산까지 허용된다고 생각하고 풀어야 한다. 정확한 답을 구해내려면 완전탐색 유형으로 접근하여 모든 경우의 수를 다 따져본 후 가장 최선의 답을 고르면 되겠지만, 입력이 최대 10만이므로 이 방법은 효율적이지 않다. 따라서 위의 문제를 풀기 위해서는 현재 상황에서 지금 당장 좋은 것만 고르는 그리디 알고리즘으로 풀어야 한다. 그리디 알고리즘이 언제나 최적의 해를 보장하는 것은 아니지만 많은 문제에 대한 해를 보다 효율적으로 구해낼 수 있다. 위의 문제는 그리디 알고리즘의 대표적인 유형 중 하나인 활동선택 문제에 해당한다. * 활동 선택 문제 : 한 번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제안된 활동들 중 가장 많은 활동을 처리할..

2021.05.17