우선순위큐4 [알고리즘] ACM Craft (백준 1005번) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 그래프 상으로 본인보다 앞서 있는 건물들이 모두 지어져야 해당 건물을 지을 수 있다는 설정을 보면 알 수 있듯이 위상 정렬을 쓰는 문제다. 다만 건물 건설 시간이 각각 다르다보니 기교를 가해야한다. 결론적으론 '위상정렬 + DP' 문제다. Solution 1. topologicalSort 함수 static int topologicalSort(int N, int W, int[] complete_time, ArrayList graph, int inEdge[].. 2020. 10. 5. [알고리즘] 후보 추천하기 (백준 1713번) 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 � www.acmicpc.net 시뮬레이션 + 자료구조를 적절히 활용하는 문제이다. 우선순위 큐를 만들어서 정해놓은 큐의 최대 크기를 넘어서면 가장 우선순위가 낮은 요소부터 제거하는 원리의 문제다. 물론 문제 자체가 쉬워서 여러 풀이가 가능하지만 정렬을 활용해야한다는 점은 변함없다. Solution 학생마다의 추천수를 보관하는 recommendation, 사진 게시 시기를 나타내는 time 우선순위 큐의 정렬 기준은 recommendation이 가장 작을 수록, time이 가장 작을 수.. 2020. 9. 20. [알고리즘] 이중우선순위큐 (프로그래머스 Level3) 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 기본적으로 우선순위큐는 Heap을 통해서 구현된다. 하지만 자바에는 기본적으로 PriorityQueue가 구현이 되어있으므로 우선순위큐 자체에는 신경쓸 필요가 없고, 이중우선순위큐라는 점에 주목해야한다. 이 말인 즉슨, 한 큐에서 최대값을 반환, 최소값을 반환하는 두 가지 작업이 동시에 가능해야된다는 점이다. Solution 우선 각각 최대값, 최소값을 반환하는 PriorityQueue 2개를 만들었다. 하지만 데이터를 삭제할 때, 2개의 큐를 모두 동기화시킬 필요가 있다. 때문에 HashMap을 사용했다. HashMap의 Key값은 삽입된 데이터, Value는 현재 큐에 들어있는 해당 데이터의 개수를 의미한다. 이 후에 삽입 때는 특별한.. 2020. 9. 8. [자바] PriorityQueue (우선순위 큐) Java Platform SE 8 docs.oracle.com PriorityQueue (우선순위 큐) 자료구조의 우선순위 큐를 자바 컬렉션 프레임워크에서 구현한 클래스이다. Queue 인터페이스를 구현하고 있다. 기본 정렬 조건(오름차순)에 의해 정렬되거나 혹은 선언 단계에서 Comparator를 삽입해서 정렬 조건을 설정할 수 있다. 내부적으로 heap의 구조를 사용하기에 enqueue (offer, add), dequeue (remove, poll)에 O(log n)의 시간이 걸린다. contains(object), remove(object)에는 O(n)의 시간이 걸린다. peek(), element(), size() 에는 O(1)의 시간이 걸린다. Queue queue = new PriorityQ.. 2020. 9. 6. 이전 1 다음
