[C/C++] 백준 #1966 프린터 큐(구현)
네트워크 프린터에서는 전해진 문서들이 큐에 쌓이고, 차례대로 찍히는 것이 일반적입니다. 이 문제에서의 프린터 큐는 중요도가 있어서, 중요도가 높은 것이 후위에 있으면, 해당 문서를 찍지 않고, 큐의 마지막으로 옮겨지게 됩니다. 이번 백준 문제는 이러한 시스템에서 m번째 문서가 몇번째 찍히는지 계산하는 것입니다. 문제 뜻대로 그대로 구현을 한다면, 큐에서 문서를 하나 빼낼때마다, 매번 뒤의 문서들을 검색해야 합니다. 이 경우 우선순위가 낮은 것부터 높은것 순서대로 되어 있는 최악의 경우라면, 문서를 검사하는 비용이 \(O(N^2)\)이 됩니다. 사실 N이 100 이하이므로 이렇게 구현을 해도 됩니다. 검사비용말고, 큐에 추가하는 것을 따진다면, 최악의 경우 역시 \(O(N^2)\)이므로, 검사비용이 낮아지..
2022. 12. 14.
[C/C++] 백준 #1946 신입 사원(탐욕 기법)
신입사원의 채용 기준은 다른 모든 면접자들의 성적과 비교해서 하나라도 우수한 직원을 뽑는 것입니다. 문제의 뜻을 잘 이해하지 않으면 풀기 어려운 문제입니다. 성적은 두가지가 있는데, 이 두가지의 성적은 모두 동차 없이 순위가 정해집니다. N명의 면접자가 있다면, 1위부터 N위까지말이죠. 예를 들어서 3명의 면접자가 있고, 순위가 (1, 3) (2, 2) (3, 1) 이었다면, (1, 3)위 한 사람은 다른 두 직원에 비해서 첫번째 성적이 좋으므로 채용됩니다. (2, 2)한 면접자는 (1, 3) 면접자에 비해서는 두번째 시험성적이, (3, 1) 면접자에 비해서는 첫번째 시험성적이 좋아서 채용되죠. (3, 1) 면접자는 다른 두 면접자에 비해서 두번째 성적이 좋아서 채용됩니다. 이것을 저는 탐욕적 기법을 통..
2022. 11. 29.
