분류 전체보기215 백준 2075: N번째 큰 수(java) 문제풀이 우선순위 큐를 이용하면 쉽게 풀 수 있다. N*N개의 수를 모두 우선순위 큐에 삽입하고 (N-1)개의 요소를 삭제한 뒤 N번째 요소를 출력하면 된다.N번째로 큰 수를 출력해야 하므로 최대 우선순위 큐를 사용하고, 이를 위해 PriorityQueue 객체 생성 시 Comparator.reverseOrder()를 지정해야 함에 주의하자. 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Comparator;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main .. 2024. 8. 24. 백준 11279: 최대 힙(java) 문제풀이 최대 우선순위 큐를 이용하는 문제이다. PriorityQueue 객체 생성 시 내림차순 정렬하는 것을 제외하면 1927번 문제와 풀이 방식이 동일하다. 내림차순 정렬을 위해 Comparator.reverseOrder()을 사용한다.PriorityQueue queue=new PriorityQueue(Comparator.reverseOrder()); 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Comparator;import java.util.PriorityQueue;public class Main { public static void main(.. 2024. 8. 24. 백준 1927: 최소 힙(java) 문제풀이 우선순위 큐(priority queue)를 이용하는 문제다. 배열에서 가장 작은 수를 출력해야 하므로 최소 우선순위 큐를 사용한다. PriorityQueue 클래스를 이용하면 별도의 큐 구현 과정 없이 간단하게 풀이할 수 있다. PriorityQueue 객체에서 요소를 poll하면 자동으로 가장 작은 값이 반환되므로, N만큼 반복하며 0이 입력되면 poll하고 아니라면 offer해주기만 하면 끝난다. 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;public class Main { public static void ma.. 2024. 8. 24. 히프 히프(heap) 개념- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리- 여러 개의 값들 중 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조- 히프 트리에서는 중복된 값을 허용(완전 이진 트리에서는 허용 x)- "느슨한 정렬 상태 유지": 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도- 삭제 연산마다 가장 큰 값을 찾아내기만 하면 되므로 완전히 정렬할 필요 x- 히프는 완전 이진 트리히프의 종류- 2가지의 히프 트리 존재 1. 최대 히프(max heap)- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리- key(부모 노드) ≥ key(자식 노드) 2. 최소 히프(min heap)- 부모 노드의 키 값이 자식 노드의 키 값보다 .. 2024. 8. 24. 우선순위 큐의 구현 배열을 사용하는 방법 1. 정렬되지 않은 배열 사용- 배열의 맨 끝에 새로운 요소를 추가- 삽입 시의 시간 복잡도는 O(1)- 삭제 시 우선 순위가 가장 높은 요소를 찾아야 함- 정렬되어 있지 않으므로 배열의 처음부터 끝까지 모든 요소를 스캔- 삭제 시의 시간 복잡도는 O(n) - 요소 삭제 후, 삭제된 요소 뒤에 있는 요소들을 앞으로 이동시켜야 함 2. 정렬된 배열 사용- 요소 삽입 시, 다른 요소와 값을 비교하여 적절한 삽입 위치를 결정- 삽입 위치 뒤의 요소들을 이동시켜 빈자리를 만든 다음 삽입- 삽입 시의 시간 복잡도는 O(n)- 삭제 시 맨 앞 또는 맨 뒤의 요소를 삭제하면 됨- 삭제의 시간 복잡도는 O(1)연결 리스트를 사용하는 방법- 배열을 사용한 방법과 유사 1. 정렬되지 않은 연결 리스트.. 2024. 8. 24. 우선순위 큐 우선순위 큐- 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 됨- 우선순위 큐는 데이터들이 우선 순위를 가지고 있고, 우선 순위가 높은 데이터가 먼저 나가게 됨- 적절한 우선 순위를 부여하여 우선순위 큐를 스택이나 큐로 사용할 수 있음- 우선순위 큐는 0개 이상의 요소의 모임- 각 요소들은 우선 순위 값을 가지고 있음- 우선순위 큐는 최소 우선순위 큐와 최대 우선순위 큐로 나뉨최소 우선순위 큐: 우선 순위가 낮은 요소를 먼저 삭제최대 우선순위 큐: 우선 순위가 높은 요소를 먼저 삭제 2024. 8. 24. 이전 1 ··· 8 9 10 11 12 13 14 ··· 36 다음
