우선순위큐 검색 결과

해당 글 4건
우선순위 스케줄링 aging 처리를 구현해 봅시다.

제가 세터였던 대회 문제들 중에서는 가희와 프로세스 시리즈가 있었습니다. 문제 제목을 보면 알 수 있듯, 해당 문제들은 cs 과목도 같이 복기하시면서, 코딩 테스트도 같이 준비하면 좋겠다고 생각해서 출제하게 되었습니다. 무엇을 물어보려고 저는 이 문제를 냈을까요? 눈치가 빠르신 분들은 아셨을 지도 모르겠지만, 영상에서 언급된 aging에 대해서 냈음을 알 수 있습니다. 여기서 조금 더 나가서, 상황을 일반화 시킬 수 있는지 묻기 위해서, 7번과 8번 문제도 같이 냈습니다. 기술 면접을 준비하시기 위해서 cs 과목들을 보셨다면, 우선순위 큐를 들어보셨을 겁니다. 문제에서 우선순위가 가장 높은 것을 선택한다는 것이 언급되었으니, 먼저 의심해 봐야 할 것은 우선 순위 큐를 써야 하나? 입니다. 혹은 정렬을 쓸..
구현 2021. 6. 28. 03:34
java priority queue 예제 : 비교자만 잘 작성해 봅시다.

java에서 어떻게 Priority Queue를 쓸까요? 예제로 간단하게 알아보도록 하겠습니다. 먼저, 기본적으로 Comparable이 구현이 되어 있는 경우에는, 따로 compareTo를 정의하지 않아도, 알아서 우선순위가 높은 것 부터 빠져나옴을 알 수 있어요. 예를 들자면 String 클래스의 경우에는 다음과 같이 선언이 되어 있습니다. 여기서 중요한 것은 Comparable입니다. 비교 가능하다는 것입니다. 그러면 내부에 compareTo가 정의가 되어 있을 겁니다. 보니까 정의가 되어 있네요. 예제 프로그램 1을 봅시다. 보통 pq를 구현할 때, 이런 식으로 많이 구현합니다. pq가 비었는지 확인하기 위해서, isEmpty를 호출합니다. 그리고, 맨 위에 있는 원소를 꺼내기 위해서 poll 메서..
레퍼런스/예제 2021. 2. 22. 07:00
우선순위 큐 : 부모가 자식들보다 rank가 높다.

우선순위 큐는, 삽입과 삭제가 일어날 때, 가장 우선순위가 높은 것을 빠르게 찾을 수 있는 구조입니다. 일단, 이것의 특징 먼저 간단하게 잡고 넘어가 봅시다. 먼저, 부모들은 자식들보다 rank가 높습니다. 예를 들어서, A의 자식이 B, C라고 해 봅시다. 그러면, A >= B이고 A >= C입니다. 그러면 A의 모든 child들 (자식의 자식이라던지)은 무조건 A보다 rank가 같거나 낮을까요? 위 그림을 봅시다. B(1)의 직계 child는 B(2), B(2)의 child는 B(3), ... 이런 식으로 가고 있어요. 그러면 A >= B(1) >= ... >= B(n)이 성립합니다. 연쇄입니다. 따라서, A >= B(n)입니다. 부모에서 자식으로만 연결된 간선이 있고, x가 A로부터 도달 가능할 때..
자료알고/자료구조 2019. 12. 16. 21:56
c++ priority queue 예제 : compare 구조체만 잘 정의합시다.

priority_queue는 코딩 테스트에서 꽤 빈도 높게 출제되고 있는 자료 구조 중 하나입니다. 물론, set이나 map도 많이 보이긴 합니다. 여태까지 코딩 테스트 문제들을 쭉 보았을 때, 우선 순위 큐, 줄여서 pq를 사용해서 푸는 문제가 꽤 많이 등장하였습니다. 자료구조나, 알고리즘 시간에 반드시 한 번 쯤은 짚고 넘어가는 것을 물어보았다는 것은, 기본을 보았다는 소리입니다. 이것은 한 마디로 top 메서드를 호출했을 때, 우선 순위가 가장 높은 것을 꺼내는 구조입니다. 그것이 전부입니다. 하지만, 그러한 작업과, 삽입, 삭제가 O(log)가 보장됩니다. 왜 그런지는 자료 구조 시간에 다시 언급해 드리도록 하겠습니다. 일단, 오늘은 log라는 것만 머릿속에 넣으시면 되겠습니다. 보통 저는 pq를..
레퍼런스/예제 2019. 10. 22. 00:45