본문 바로가기

분류 전체보기215

히프 정렬 히프 정렬(heap sort): 히프를 사용하는 정렬 알고리즘- 최대 히프를 이용하여 n개의 요소를 O(nlog₂n)의 시간 복잡도로 정렬- 정렬되지 않은 1차원 배열이 존재할 때, 배열의 데이터들을 차례대로 최대 히프에 추가- 한 번에 하나의 요소를 히프에서 꺼내 배열의 뒤쪽부터 저장- 배열은 오름차순으로 정렬됨 히프 정렬 복잡도- 히프 트리의 전체 높이는 log₂n이므로 하나의 요소를 히프에 삽입하거나 삭제할 때 히프 재정비에 log₂n만큼의 시간 소요- 요소의 개수가 n개일 때 전체적으로 O(nlog₂n)의 시간 소요- 삽입 정렬 알고리즘 시간 복잡도가 O(n²)인 것에 비해 효율적- 히프 정렬은 전체 자료 정렬 보다는 가장 큰 값 몇 개만이 필요할 때 가장 유용히프 정렬 구현#include #in.. 2024. 8. 26.
히프의 구현 - 히프는 1차원 배열로 표현될 수 있음- 히프의 각 요소들을 구조체 element로 정의하고, element의 1차원 배열을 만들어 히프 구현#define MAX_ELEMENT 200typedef struct { int key;} element;typedef struct { element heap[MAX_ELEMENT]; int heap_size; //현재 히프 안에 저장된 요소 개수} HeapType; - 히프를 생성하려면 아래와 같은 방법을 사용HeapType heap;HeapType* heap = create(); //동적 할당 이용삽입 연산- 히프에 새로운 요소가 들어오면, 일단 새로운 노드를 히프의 마지막 노드로 삽입- 삽입 후에 새로운 노드를 부모 노드들과 교환하여 히프의 성질을 만족하도록 .. 2024. 8. 25.
백준 31860: 열심히 일하는 중(java) 문제풀이 우선순위 큐를 이용하는 문제다.PriorityQueue queue=new PriorityQueue(Comparator.reverseOrder());우선순위 큐 queue를 생성하되, 중요도가 높은 일부터 먼저 처리하게끔 해야 하므로 Comparator.reverseOrder()를 지정해야 한다.  이후 queue에서 poll한 값을 K와 비교해 K 이하일 경우 삭제된 채로 continue하고, K 초과일 경우 이 값에서 M만큼 뺀 값을 다시 queue에 삽입한다. 위 과정을 queue가 공백 상태가 될 때까지 반복하고, 한 번 반복할 때마다 count를 1씩 증가시킨다.import java.io.BufferedReader;import java.io.IOException;import java.io.. 2024. 8. 25.
백준 28107: 회전초밥(java) 문제풀이 손님 큐와 초밥 큐, 2개의 우선순위 큐를 이용해 풀이한다. customer 우선순위 큐에 { 초밥 종류, 손님 번호 }를 원소로 가지는 배열을 삽입한 후 초밥 종류에 따라 오름차순으로 정렬하고, 같은 종류의 초밥일 경우 손님 번호 순으로 정렬한다.PriorityQueue customer=new PriorityQueue(new Comparator() { @Override public int compare(int[] o1, int[] o2) { if(o1[0]==o2[0]) { //같은 초밥일 경우 return o1[1]-o2[1]; //손님 순서로 정렬 } return o1[0]-o2[0]; //초밥 종류로 정렬 }}); 이때 Comparator 수정을 통해 정렬 규칙을 추가해 .. 2024. 8. 25.
백준 11286: 절댓값 힙(java) 문제풀이 작은 수부터 출력해야 하므로 최소 우선순위 큐로 풀이하되, 절댓값은 같지만 부호가 다를 경우 순서를 조정해야 하므로 Comparator를 수정한다.class NewComparator implements Comparator{ @Override public int compare(Integer o1, Integer o2) { if(Math.abs(o1)>Math.abs(o2)) { //o1의 절댓값이 더 크면 자리 변경 return Math.abs(o1)-Math.abs(o2); } else if(Math.abs(o1)==Math.abs(o2)) { //절댓값이 동일하면 음수를 앞으로 보냄 return o1-o2; } else { return -1; .. 2024. 8. 24.
백준 23757: 아이들과 선물 상자(java) 문제풀이 우선순위 큐를 사용해 쉽게 해결할 수 있다. 선물이 가장 많이 담겨있는 상자부터 열어야 하므로 최대 우선순위 큐를 사용하고, PriorityQueue 객체 생성 시 내림차순 정렬을 위해 Comparator.reverseOrder()을 지정한다. 누군가 선물을 가져갔던 상자에서 또다시 가져가도 된다는 점에만 주의하면 된다. 원하는 만큼(n) 선물을 가져간 후(poll) 남은 상자는 다시 정렬에 포함시켜야 하므로(add) 아래와 같이 작성할 수 있다.queue.add(queue.poll()-n); 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Co.. 2024. 8. 24.

티스토리툴바