한 방에 N개의 회의 시작 시간과 끝시간을 주었을 때, 회의가 겹치지 않으면서 최대한 많은 회의를 할 때의 회의 수를 찾는 문제이다.
처음엔 복잡하게생각해서 이러저러한 알고리즘을 찾아 다녔는데, 다시 생각해보니 간단했다.
회의 들을 끝 시간을 기준으로 오름차순으로 정렬한 뒤, 처음의 끝시간을 max로 잡고 반복하면서 max값과 다른 회의의 시작 시간을 비교해줘서 max값 이상이면, 다시 max를 그 회의의 끝시간으로 잡는다. 이렇게 max값이 갱신될 때 마다 카운트 해주면 답을 구할 수 있다.
소스
질문이 있습니다. 정렬을 사용할 경우 퀵정렬을 사용한다고 가정한다면 O(NlogN)의 시간이 더 들어가는데 그리디 알고리즘 본연의 효율보다 더 큰 시간이 소요되는 것이 아닌가 생각이 듭니다. 정렬을 사용하지 않고 해결하는 방법이 있을까요?
답글삭제그리디는 정형화된 알고리즘이 아니라 알고리즘적 패러다임입니다.
삭제DP의 시간복잡도가 항상 정해진것이 아닌것처럼, 그리디의 시간복잡도도 정해진것이 아닙니다.
그리디가 최적해를 보장하는 유명한 알고리즘인 다익스트라를 예로 들어보면,
거리가 가장 짧은 간선을 찾는 과정이 필요합니다.
여기서 우선순위 큐를 사용하면 log 시간에 원하는 간선을 구할 수 있지만, naive하게 반복문을 통해서 찾으면 선형시간에 구할 수 있죠.
하지만 두 방법 모두 다익스트라 알고리즘이며, 후자가 쓰이는 경우도 종종있습니다.
즉, 그리디 알고리즘은 한번에 연산으로 무언가를 택하는것이 아닌, 어떤 과정으로 택하다보면 답이 나오는것을 말합니다. 두 말의 차이는 전자는 택할때의 시간복잡도가 O(1)이 되는것이고, 후자는 시간복잡도와는 연관이 없습니다.
따라서 그리디 알고리즘 본연의 효율이라는 표현은 적절치 않은것 같습니다. 이 문제에서 정렬을 사용한 이유는, 정렬을 수행해주면 각 회의 일정을 순차적으로 보면서 그리디를 수행할 수 있기 때문입니다.
이 문제를 해결한 다른 분들의 풀이를 참고해 보았는데 O(NlgN) 풀이보다 빠른 코드는 없는것 같습니다.